# 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 V
_{1}, V_{2}, V_{3},....,V_{N}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.

### Shortest-path Problems

- There are different kinds of shortest-path problems.
**The single source shortest-path problem**is used to find minimum cost from single source to all other vertices.**The all-pairs shortest-path problem**is 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.

### 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.
- d
_{v}--keeps distance from source s. Initially all vertices are ∞ except source s. - p
_{v}--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, d
_{v}is ∞ and p_{v}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 d
_{w}=d_{v}+ C_{v, w}where C_{v, w}is the cost or weight on the edge of the adjacent vertex. - Next, pick up the vertex V who has the smallest distance d
_{v}among all the unknown vertices. - Then declare that the shortest path from s to v is known. Again update the distance value d
_{v}of all the adjacent vertices of v by using d_{w}=d_{v}+ C_{v, w}. - If the new value d
_{w}is greater than the old one, then we simply ignore that value otherwise we will insert the new value into the d_{v}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.

#### Step 1

First, we select the source vertex as V_{1}, with path length 0 and we set known value to 1 and update the distance value of adjacent vertices such as V_{2}, V_{3}, and V_{4}.

#### Step 2

Next, V_{3} is selected and set known value to 1 and update the adjacent vertices V_{4} and V_{6}. Actually, V_{4} is already reached with cost of 8, but the cost of going through v_{3} will be 3 which is smaller than the previous cost. So we can replace that old one with new distance value.

#### Step 3

Next, V_{4} is selected and marked known. The vertices V_{2}, V_{5} and V_{6} are adjacent. The vertex V_{2} is adjacent but not adjusted, because the cost of going via V_{4} is 3+2=5 which is greater than the previous distance 4. So simply discards the new value. Similarly for V_{6}, the cost is changed to 5.

#### Step 4

Next, V_{2} is selected and marked known. V_{5} is the only adjacent vertex which is adjusted to 9(4+5) < 10.

#### Step 5

Next, selected vertex is V_{6} and marked known. V_{7} is the only adjacent vertex which is adjusted to 8(5+3).

#### Step 6

Next, selected vertex is V_{7} and set known to 1. V_{4} is adjacent but already known, so no work is done on it.

#### Step 7

Finally, V_{5} 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.