Content deleted Content added
Line 21:
From what I understand, there may be many more than a single shortest path (think of two equal routes), and Bellman-Ford is guaranteed to find one of them. Thus an infinite number of equal shortest paths is not a problem. The issue with negative weight cycles is that you can always find a better path by adding one more cycle to the path and as such there is no shortest path. [[User:Kyeprime|kyeprime]] ([[User talk:Kyeprime|talk]]) 19:17, 21 April 2010 (UTC)
In every finite graph, there is only a finite number of paths, because no path may visit a vertex or an edge twice. Therefore, there is only a finite number of shortest paths, too. However, finding a shortest path in graphs with arbitrary edge-weights is NP-hard. [[User:Morgurth|Morgurth]] ([[User talk:Morgurth|talk]]) 12:13, 1 November 2011 (UTC)
== Counting to infinity ==
| |||