Editorial for Shortest Path Recovery

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.


    43% Solution Ratio

    mohanr7073Earliest, 3M ago

    CoderAnshuFastest, 0.0s

    Um_nikLightest, 131 kB

    Deshi_TouristShortest, 811B

    Toph uses cookies. By continuing you agree to our Cookie Policy.