diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/dijkstra.cpp | 20 | ||||
| -rw-r--r-- | graph/graph.tex | 5 |
2 files changed, 25 insertions, 0 deletions
diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp new file mode 100644 index 0000000..e7ec0c3 --- /dev/null +++ b/graph/dijkstra.cpp @@ -0,0 +1,20 @@ +priority_queue<ii, vector<ii>, greater<ii> > pq; +vector<int> dist; +dist.assign(NUM_VERTICES, INF); +dist[0] = 0; +pq.push(ii(0, 0)); + +while (!pq.empty()) { + di front = pq.top(); pq.pop(); + int curNode = front.second, curDist = front.first; + + if (curDist > dist[curNode]) continue; + + for (i = 0; i < (int)adjlist[curNode].size(); i++) { + int nextNode = adjlist[curNode][i].first, nextDist = curDist + adjlist[curNode][i].second; + + if (nextDist < dist[nextNode]) { + dist[nextNode] = nextDist; pq.push(ii(nextDist, nextNode)); + } + } +}
\ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index 4646ee3..2bf395c 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -2,7 +2,12 @@ \subsection{Kürzeste Wege} +\subsubsection{Algorithmus von \textsc{Dijkstra}} +Kürzeste Pfade in Graphen ohne negative Kanten. +\lstinputlisting{graph/dijkstra.cpp} + \subsubsection{\textsc{Bellmann-Ford}-Algorithmus} +Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \lstinputlisting{graph/bellmannFord.cpp} \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} |