What algorithm to apply when a graph have cycles ("circuits") and some negatives values in order to find the shortest path from $x1$ to all vertices? For instance in the following graph? I know I can't use Djikstra...

enter image description here

  • $\begingroup$ Maybe you can add minimal value to all edges? Would it help? Flagging visited vertices to avoid infinite loop? If you cannot use algorithm X, but it is close enough, try resolving issues, and try again. No negative? Remove them... $\endgroup$ – Evil Jan 2 '16 at 1:40

The Floyd-Warshall algorithm gives costs between all pairs of vertices in reasonable time ($O(n^3)$ for $n$ vertices) as long as there are no negative cost cycles.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.