Shortest Path Algos

Shortest path algos playlist

Dijkstra's

• Video
• Note: shortest path from one node to all nodes
• h/t Aladdin Persson – GitHub | YouTube

❯ python dijkstras.py
Shortest path from A: {'A': 0, 'B': 3, 'C': 2, 'D': 5, 'E': 6}
Shortest path from A using heap: {'A': 0, 'B': 3, 'C': 2, 'D': 5, 'E': 6}

Bellman-Ford

• Videos: Theory | Example
• Note: shortest path from one node to all nodes, negative edges allowed (but not negative cycles)

❯ python bellman_ford.py
Shortest path from S: {'S': 0, 'A': 5, 'B': 5, 'C': 7, 'D': 9, 'E': 8}
Shortest path from S: INVALID - negative cycle detected

Floyd-Warshall

• Video
• Note: shortest path between all pairs of vertices, negative edges allowed (but not negative cycles)

❯ python floyd_warshall.py
Shortest path matrix:

[0, -1, -2, 0]
[4, 0, 2, 4]
[5, 1, 0, 2]
[3, -1, 1, 0]