equal
deleted
inserted
replaced
21 |
21 |
22 /// \ingroup shortest_path |
22 /// \ingroup shortest_path |
23 /// \file |
23 /// \file |
24 /// \brief Bellman-Ford algorithm. |
24 /// \brief Bellman-Ford algorithm. |
25 |
25 |
|
26 #include <lemon/list_graph.h> |
26 #include <lemon/bits/path_dump.h> |
27 #include <lemon/bits/path_dump.h> |
27 #include <lemon/core.h> |
28 #include <lemon/core.h> |
28 #include <lemon/error.h> |
29 #include <lemon/error.h> |
29 #include <lemon/maps.h> |
30 #include <lemon/maps.h> |
30 #include <lemon/path.h> |
31 #include <lemon/path.h> |
773 /// \brief Gives back a negative cycle. |
774 /// \brief Gives back a negative cycle. |
774 /// |
775 /// |
775 /// This function gives back a directed cycle with negative total |
776 /// This function gives back a directed cycle with negative total |
776 /// length if the algorithm has already found one. |
777 /// length if the algorithm has already found one. |
777 /// Otherwise it gives back an empty path. |
778 /// Otherwise it gives back an empty path. |
778 lemon::Path<Digraph> negativeCycle() { |
779 lemon::Path<Digraph> negativeCycle() const { |
779 typename Digraph::template NodeMap<int> state(*_gr, -1); |
780 typename Digraph::template NodeMap<int> state(*_gr, -1); |
780 lemon::Path<Digraph> cycle; |
781 lemon::Path<Digraph> cycle; |
781 for (int i = 0; i < int(_process.size()); ++i) { |
782 for (int i = 0; i < int(_process.size()); ++i) { |
782 if (state[_process[i]] != -1) continue; |
783 if (state[_process[i]] != -1) continue; |
783 for (Node v = _process[i]; (*_pred)[v] != INVALID; |
784 for (Node v = _process[i]; (*_pred)[v] != INVALID; |