1 Bellman-Ford The Bellman-Ford algorithm can be used to find the shortest path tree from a single vertex. It is similar to Dijkstra’s algorithm, in that regard, but it works on graphs with negative edges. Negative cycles, if found, cause the program to terminate since they create infinite loops. • Trace how Dijkstra’s algorithm runs on the graph below to see how it fails. • Bonus: Trace how Bellman-Ford runs and try to find ways to improve it. If we get this far, the answer is Shortest Path Faster Algorithm (SPFA) aka Yen’s improvement to Bellman-Ford It is very similar, but it only updates vertices who have been updated in the current or last iteration. If they haven’t been updated, then they cannot provide any new benefits. 2 Performace Runtime is a great measurement in theory but it doesn’t always work as well in practice. SPFA has the same runtime as Bellman-Ford, since, in the worst case a shortest path has n edges and n iterations are performed. However, since SPFA terminates once the problem is solved, the amount of time to run is reduced. A B C Dk D1 2 1 −3 1 1 Figure 1: Graph with k-claw from a to Di; 1 ≤ i ≤ k. Shortest path tree from source A is highlighted red 1
