## Introduction

This is the third post in the Graph Traversals – Online Classes.

After learning how to move through a graph, we might be interested in learning more. One interesting problem is determining the shortest path between two vertices of a graph.

The problem can be extended and defined in many other forms. I prefer to call it “minimizing the cost”. For e.g.

- When we measure the cost in terms of the distances between vertices, it can be called as the Shortest Path.
- When we measure the cost in terms of the money spent between vertices, it can be called as the Cheapest Path.
- When we measure the cost in terms of the time spent between vertices, it can be called as the Fastest Path.

There can be many more interpretations for this problem. Also, this means that the algorithm can be used to solve variety of problems and not just shortest path ones.

## Avoiding Confusions about shortest path

There are few points I would like to clarify before we discuss the algorithm.

- There can be more than one shortest path between two vertices in a graph.
- The shortest path may not pass through all the vertices.
- It is easier to find the shortest path from the source vertex to each of the vertices and then evaluate the path between the vertices we are interested in.
- This algorithm can be used for directed as well as un-directed graphs
- For the sake of simplicity, we will only consider graphs with non-negative edges.

**Note : ** This is not the only algorithm to find the shortest path, few more like Bellman-Ford, Floyd-Warshall, Johnson’s algorithm are interesting as well.

## Explanation – Shortest Path using Dijkstra’s Algorithm

The idea of the algorithm is very simple.

- It maintains a list of unvisited vertices.
- It chooses a vertex (the source) and assigns a maximum possible cost (i.e. infinity) to every other vertex.
- The cost of the source remains zero as it actually takes nothing to reach from the source vertex to itself.
- In every subsequent step of the algorithm it tries to improve(minimize) the cost for each vertex. Here the cost can be distance, money or time taken to reach that vertex from the source vertex. The minimization of cost is a multi-step process.
- For each unvisited neighbor (vertex 2, vertex 3, vertex 4) of the current vertex (vertex 1) calculate the new cost from the vertex (vertex 1).
- For e.g. the new cost of vertex 2 is calculated as the minimum of the two ( (existing cost of vertex 2) or (sum of cost of vertex 1 + the cost of edge from vertex 1 to vertex 2) )

- When all the neighbors of the current node are considered, it marks the current node as visited and is removed from the unvisited list.
- Select a vertex from the list of unvisited nodes (which has the smallest cost) and repeat step 4.
- At the end there will be no possibilities to improve it further and then the algorithm ends

For demonstration we will consider the below graph:

## Step Wise Execution

##### Step 1:

Mark Vertex 1 as the source vertex. Assign a cost zero to Vertex 1 and (infinite to all other vertices). The state is as follows:

##### Step 2:

For each of the unvisited neighbors (Vertex 2, Vertex 3 and Vertex 4) calculate the minimum cost as min(current cost of vertex under consideration, sum of cost of vertex 1 and connecting edge). Mark Vertex 1 as visited , in the diagram we border it black. The new state would be as follows:

##### Step 3:

Choose the unvisited vertex with minimum cost (vertex 4) and consider all its unvisited neighbors (Vertex 5 and Vertex 6) and calculate the minimum cost for both of them. The state is as follows:

##### Step 4:

Choose the unvisited vertex with minimum cost (vertex 2 or vertex 5, here we choose vertex 2) and consider all its unvisited neighbors (Vertex 3 and Vertex 5) and calculate the minimum cost for both of them. Now, the current cost of Vertex 3 is [4] and the sum of (cost of Vertex 2 + cost of edge (2,3) ) is 3 + 4 = [7]. Minimum of 4, 7 is 4. Hence the cost of vertex 3 won’t change. By the same argument the cost of vertex 5 will not change. We just mark the vertex 2 as visited, all the costs remain same. The state is as follows:

##### Step 5:

Choose the unvisited vertex with minimum cost (vertex 5) and consider all its unvisited neighbors (Vertex 3 and Vertex 6) and calculate the minimum cost for both of them. Now, the current cost of Vertex 3 is [4] and the sum of (cost of Vertex 5 + cost of edge (5,3) ) is 3 + 6 = [9]. Minimum of 4, 9 is 4. Hence the cost of vertex 3 won’t change. Now, the current cost of Vertex 6 is [6] and the sum of (cost of Vertex 5 + cost of edge (3,6) ) is 3 + 2 = [5]. Minimum of 6, 5 is 45. Hence the cost of vertex 6 changes to 5. The state is as follows:

##### Step 6:

Choose the unvisited vertex with minimum cost (vertex 3) and consider all its unvisited neighbors (none). So mark it visited. The state is as follows:

##### Step 7:

Choose the unvisited vertex with minimum cost (vertex 6) and consider all its unvisited neighbors (none). So mark it visited. The state is as follows:

Now there is no unvisited vertex left and the execution ends. At the end we know the shortest paths for all the vertices from the source vertex 1. Even if we know the shortest path length, we do not know the exact list of vertices which contributes to the shortest path until we maintain them separately or the data structure supports it.

## Pseudo Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function dijkstra(G, S) dist[source] <- 0 previous[source] <- NULL for each vertex V in G if V NOT S dist[V] <- infinite previous[V] <- NULL ADD V to Q \\ if we choose the Q as a Priority Queue, extracting minimum will be easy. while Q IS NOT EMPTY U <- Extract MIN from Q for each unvisited neighbour V of U tempDist <- dist[U] + edge_weight(U, V) if tempDist < dist[V] dist[V] <- tempDist previous[V] <- U return dist[], previous[] |

## Source Code – Shortest Path using Dijkstra’s Algorithm

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public class Dijkstra { public void dijkstra(Vertex source, List vertices) { source.min = 0; PriorityQueue Q = new PriorityQueue(); for(Vertex v : vertices){ Q.add(v); } while (!Q.isEmpty()) { Vertex u = Q.poll(); // Visit each edge exiting u for (Edge e : u.incidentEdges) { Vertex v = e.end; int weight = e.weight; int tempDistance = u.min + weight; if (tempDistance < v.min) { Q.remove(v); // remove to re-insert it in the queue with the new cost. v.min = tempDistance; v.previous = u; Q.add(v); } } } } |

To download the complete code please visit techieme github repository.

## Analysis of the algorithm

The outer loop runs for |V| times

The inner loop runs for |V-1| times for a complete graph as each vertex has |V-1| edges.

Also, for each iteration of the inner loop we do an extractMin and a reduceKey operation for the vertex.

Hence the total running time has an upper bound of O(|V| * |V-1|). This is the upper bound, O(|V|^{2})

Point worth noting is that the complexity will actually depend on the implementation of the data structure which is used as the Queue. We will be discussing and comparing all the running times for the three shortest path algorithms together in coming posts.

Don’t forget to subscribe to TechieMe to get updates on latest posts.