Data Structures - Shortest-Path Algorithms
For a given graph, the shortest-path algorithms determine the minimum cost of the path from source to every other vertex.
- The path is the sequence of vertices V1, V2, V3,....,VN and the cost of the path is .
- If the graph is weighted, then the cost of the path is the sum of weights on its edges.
- If the graph is not weighted, the cost of the path is the number of edges on the path.
- There are the situations in which we can use the shortest path algorithm to find the cheapest way to send the information from one computer to another.
- In real life application, we can use the graph to design the airplane and use the shortest path algorithm to find the best route between the two airports.
- There are different kinds of shortest-path problems.
- The single source shortest-path problemis used to find minimum cost from single source to all other vertices.
- The all-pairs shortest-path problemis used to find the shortest-path between all pairs of vertices.
- The single source shortest-path problem is solved by using Dijkstra's algorithm and the all-pairs shortest-path problem is solved by using Floyd-Warshall Algorithm. Let us look at Dijkstra's algorithm.
This algorithm used to solve single source shortest path problem. It follows a Greedy Algorithm. Generally greedy algorithm solves a problem in stages and it finds the solution that appears to be the optimum solution at each stage. The Dijkstra's algorithm proceeds in stage. At each stage, it finds the shortest path from source to every other vertex. For doing this, we will keep track of three pieces of information for each vertex such as
- Known--set to 1 after a vertex is processed. Initially all vertices are not known.
- dv--keeps distance from source s. Initially all vertices are ∞ except source s.
- pv--bookkeeping variable, used to print actual path.
Steps to find the shortest path
- Initially all the vertices are not known. So the entry in known value is 0, dv is ∞ and pv is 0.
- Select the source vertex 's' and set the known entry to '1' and update the distance value of all adjacent vertices of the source vertex s by using dw=dv + Cv, w where Cv, w is the cost or weight on the edge of the adjacent vertex.
- Next, pick up the vertex V who has the smallest distance dv among all the unknown vertices.
- Then declare that the shortest path from s to v is known. Again update the distance value dv of all the adjacent vertices of v by using dw=dv + Cv, w.
- If the new value dw is greater than the old one, then we simply ignore that value otherwise we will insert the new value into the dv entry.
- Repeat the steps 3, 4 and 5 until all vertices are known.
Finding Shortest path for Above Graph
Let us consider the above graph, now we want to find the shortest path from source to all other vertices using Dijkstra's algorithm.
First, we select the source vertex as V1, with path length 0 and we set known value to 1 and update the distance value of adjacent vertices such as V2, V3, and V4.
Next, V3 is selected and set known value to 1 and update the adjacent vertices V4 and V6. Actually, V4 is already reached with cost of 8, but the cost of going through v3 will be 3 which is smaller than the previous cost. So we can replace that old one with new distance value.
Next, V4 is selected and marked known. The vertices V2, V5 and V6 are adjacent. The vertex V2 is adjacent but not adjusted, because the cost of going via V4 is 3+2=5 which is greater than the previous distance 4. So simply discards the new value. Similarly for V6, the cost is changed to 5.
Next, V2 is selected and marked known. V5 is the only adjacent vertex which is adjusted to 9(4+5) < 10.
Next, selected vertex is V6 and marked known. V7 is the only adjacent vertex which is adjusted to 8(5+3).
Next, selected vertex is V7 and set known to 1. V4 is adjacent but already known, so no work is done on it.
Finally, V5 is selected and marked known. Now the Dijkstra's algorithm is terminated and print out the shortest path from a start vertex to all other vertices.