Bellman-Ford Shortest-Path Algorithm

External

• https://www.coursera.org/learn/algorithms-npcomplete/lecture/x0YZd/single-source-shortest-paths-revisted
• https://www.coursera.org/learn/algorithms-npcomplete/lecture/g8N36/optimal-substructure
• https://www.coursera.org/learn/algorithms-npcomplete/lecture/9YeyY/the-basic-algorithm-i
• https://www.coursera.org/learn/algorithms-npcomplete/lecture/WhILJ/the-basic-algorithm-ii
• https://www.coursera.org/learn/algorithms-npcomplete/lecture/AB5wH/detecting-negative-cycles
• https://www.coursera.org/learn/algorithms-npcomplete/lecture/TrNPq/a-space-optimization

Internal

• Shortest Path in a Graph
• Dynamic Programming
• Floyd-Warshall Algorithm
• Johnson's Algorithm

Overview

A dynamic programming algorithm that can compute shortest path in graphs with negative length edges. The running time complexity is O(mn).