Overview of Single Source Shortest Path

Breadth-first search (BFS) algorithm is used to find the shortest path in unweighted graphs.

For a weighted graph, the BSF doesn't work. There are two common single source shortest path algorithms.

1. Dijkstra's algorithm (only works with non-negative weights)
2. Bellman-Ford algorithm (works with any weights) --> improved version, shortest path faster algorithm

Edge relaxation is to select the shortest path between two nodes.