Bellman-Ford

Contents

Bellman-Ford#

Contents#

Bellman-Ford

A -> (B,  10), (C, 1)
B -> (C, -99)
C -> (D,   2), (E, 2)
D -> (A,   1)
E ->

Table
A    0
B    infty
C    infty
D    infty
E    infty

Assume that there are no cycles.

We know that the shortest path cannot contain a cycle.

There are a finite number of possible paths, which can be enumerated:

A -> B               10
A -> B -> C         -89
A -> B -> C -> D    -87
A -> B -> C -> E    -87
A -> C                1
A -> C -> D           3
A -> C -> E           3

Although the graph contains just 6 edges, the number of edges in all possible paths is 14. In the worst case in which every vertex is connected to every other vertex the number of edges in all possible paths is exponential. Therefore, finding the shortest path by traversing all possible paths is an exponential time algorithm.

The edge A -> B shows up in four possible paths. Use memoization to remember this traversal

Resources#

https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/

Contents