# Shortest Path Problems

Tags: AlgorithmGiven a weighted graph `G`

Given a weighted graph` G (V,E), =(V,E),`

and a source vertex` s`

, find the minimum weighted path from `s`

to every other vertex in `G`

### Unweighted graph

If the graph is unweighted, we can solve this problem using Bread First Search.

1 2 3 4 5 |
For each vertex, keep track of Whether we have visited it ( Whether we have visited it (known) Its distance from the start vertex (dv) Its predecessor vertex along the shortest Its predecessor vertex along the shortest path from the start vertex (pv) |

### Weighted Graph

For Weighted Graph, we solve this problem use Dijkstra’s algorithm.

1 2 3 4 5 6 7 8 9 10 11 12 13 |
S: set of vertices for which the shortest path length from s is known. Invariant: for v in S, dist[v] is the length of the shortest path from s to v. Initialize S to s, dist[s] to 0, dist[v] to for all other v Repeat until S contains all vertices connected to s find e with v in S and w in S’ that minimizes dist[v] + e.weight() relax along that edge • add w to S |

### shortest path between all pairs of vertices

Given G(V,E), find a shortest path between all pairs of vertices.

`Solutions`

: (brute -force) Solve Single Source Shortest Path for each vertex as source. There are more efficient ways of solving this problem (e.g., Floyd problem (e.g., `Floyd -Warshall algorithm)`

.

To be continued