# Dijkstra's Algorithms

## Dijkstra's Algorithm - Shortest Path First Algorithm

Dijkstra's 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 for a vertex after it is processed. Initially all vertices are not known.
- d
_{v}= keeps distance of the vertex from source s. Initially all vertices are ∞ except source s. - p
_{v}= book keeping variable, used to print actual path.

### Steps to find the shortest path

- Initially cost associated with none of the vertices are known. So the entry in "known" value for a vertex is 0, d
_{v}is ∞ and p_{v}is 0. - Select the source vertex 's' and set the known entry to '1'
- Update the distance value of all adjacent vertices of the source vertex s by using
d

where C_{w}=d_{v}+ C_{v, w}_{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.