diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/bellmannFord.cpp | 18 | ||||
| -rw-r--r-- | graph/graph.tex | 5 |
2 files changed, 23 insertions, 0 deletions
diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp new file mode 100644 index 0000000..94fa034 --- /dev/null +++ b/graph/bellmannFord.cpp @@ -0,0 +1,18 @@ +//n = number of vertices, edges is vector of edges +dist.assign(n, INF); dist[0] = 0; +parent.assign(n, -1); +for (i = 0; i < n - 1; i++) { + for (j = 0; j < (int)edges.size(); j++) { + if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) { + dist[edges[j].to] = dist[edges[j].from] + edges[j].cost; + parent[edges[j].to] = edges[j].from; + } + } +} +//now dist and parent are correct shortest paths +//next lines check for negative cycles +for (j = 0; j < (int)edges.size(); j++) { + if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) { + //NEGATIVE CYCLE found + } +} diff --git a/graph/graph.tex b/graph/graph.tex index 53cfb2a..4646ee3 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -1,5 +1,10 @@ \section{Graphen} +\subsection{Kürzeste Wege} + +\subsubsection{\textsc{Bellmann-Ford}-Algorithmus} +\lstinputlisting{graph/bellmannFord.cpp} + \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} \lstinputlisting{graph/scc.cpp} |