Best Order to traverse a Bellman-Ford Algorithm to achieve minimum number of iterations?

What is the Best order of traversing edges within Bellman-Ford algorithm, in order to achieve a minimum number of ite开发者_StackOverflow社区rations that are necessary?

If the graph is acyclic the best way is traverse the vertices in topological order. This means only one iteration of the algorithm is necessary.

For cyclic graphs without negative edges you can use a generic shortest path algorithm as described in this pdf (sssp.pdf) with a Fifo queue, this can visit fewer vertices than the standard Bellman-ford algorithm which loops over vertices and then edges. In practice the Fifo queue approach is often faster than using a priority queue (Dijkstra) as mentioned in this answer ( Are there faster algorithms than Dijkstra? ). However, a dis-advantage of this approach is the unlike the standard Bellman-ford algorithm this algorithm will not terminate if the graph has negative cycles.

We can't generalize the best order of traversing so that no. of iterations are minimum as best order of traversing will vary from graph to graph but yes you will get the Single Source Shortest Paths in at most |V|-1 iterations. No graph would require more than |V|-1 iterations and if distance further decreases after |V|-1 iterations then it means that graph contains a negative edge cycle.