If a Bellman-Ford algorithm is run for n-1 iterations on a graph that does have shortest paths from the source nodes to all the other nodes, then by the end of the n-1’th iteration, all the shortest paths can be found. Since any edges of the given graph can have a weight from -1000 to 1000 and the graph has 500 nodes, it’s easy to see what could be the highest or lowest cost of a valid shortest path from source to any other node. Bellman-Ford also signals the existence of a cycle if the n’th iteration is performed. Thus, understanding and applying the principles of Bellman-Ford algorithm is enough to solve this problem. Since the original graph is not given and the graph may have self self, some tricky cases may arise.

Statistics

41% Solution Ratio
mohanr7073Earliest, Jun '21
mbsabbirr127Fastest, 0.0s
Um_nikLightest, 131 kB
steinumShortest, 515B
Toph uses cookies. By continuing you agree to our Cookie Policy.