Given 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.

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.

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.
[Read More...]