Shortest Path ProblemsTags: Algorithm
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
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)
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. There are more efficient ways of solving this problem (e.g., Floyd problem (e.g.,
Floyd -Warshall algorithm).
To be continued