Finding shortest path between two vertices has many applications be it in the field of navigation, networking or any other field.

In this post we are going to discuss about **Dijkstra's Algorithm** which is one of the most widely used algorithm for this purpose.

**Note** : In all the pseudo codes, 0-based indexing is used and the indentations are used to differentiate between block of codes.

## Problem Statement

Let G be a **weighted directed graph** with ** positive** weights (no

**), V be the set of all vertices and**

**negative**weights**src**be a vertex in the set V. Find the length of the shortest weighted path in G between every vertex in V and src.

## Naive Approach

The easiest approach to find shortest path between two vertices **a** and **b** is to traverse every path between the two vertices and compare them against each other. We use this approach along with a **for** loop to find the shortest path between src and every other vertex.

*Pseudo Code : *

```
minDistance[|V|]={inf}
visited[|V|]={false}
findShortestPath(curr, dest, pathTillNow)
if curr==dest
minDistance[dest]=min(minDistance[dest], pathTillNow)
return
visited[curr]=true
for child in graph[curr]
if visited[child]==true
continue
findShortestPath(child, dest, pathTillNow+graph[curr][child]
visited[curr]=false
naiveApproach(src, |V|)
for vertex=0 upto |V|
findShortestPath(src, vertex, 0)
```

**Time Complexity : O(|V|*( |V|+|E| ))**

**Space Complexity : O(|V|)**

## Dijkstra's Algorithm

Dijkstra's Algorithm is an algorithm for finding the shortest path between vertices in a graph, published by computer scientist **Edsger W. Dijkstra** in 1959.

Dijkstra's Algorithm is a **Greedy Algorithm **which makes use of the fact that **every part of an optimal path is optimal** i.e. if there exists three vertices **a**, **b** and **c** and if the optimal path between a and b passes through c or **a→....→c→....→b **be the optimal path between a and b then **a→....→c** and **c→....→b** are also optimal.

This can be easily proven by using

The algorithm expands on the aforementioned observation. Starting from the **src** vertex, we go on exploring every child of a vertex and push not previously visited vertices into a list for considering later. In the mean time, we also check if a given child vertex lies on the optimal path between the src vertex and a destination vertex.

*Pseudo Code : *

```
dijkstra(graph, V, src)
minDistance[|V|]={inf}
minDistance[src]=0
unvisitedVertices=[]
unvisitedVertices.push(src)
visited[|V|]={false}
for vertex in unvisitedVertices
visited[vertex]=true
for child in graph[vertex]
if visited[child]==true
continue
ctr=graph[vertex][child]+minDistance[vertex]
if ctr<minDistance[child]
minDistance[child]=ctr
unvisitedVertices.push(child)
return minDistance
```

**Time Complexity : O(|V|+|E|)**

**Space Complexity : O(|V|)**

**Note** : With a slightly modified version of the above mentioned algorithm we can also find the **path** and not only the weight of the shortest path. The following *pseudo code* presents the variation.

```
dijkstra(graph, V, src)
// predecessor[] will store the parent of the child in the Optimal Path
predecessor[|V|]={}
minDistance[|V|]={inf}
minDistance[src]=0
unvisitedVertices=[]
unvisitedVertices.push(src)
visited[|V|]={false}
for vertex in unvisitedVertices
visited[vertex]=true
for child in graph[vertex]
if visited[child]==true
continue
ctr=graph[vertex][child]+minDistance[vertex]
if ctr<minDistance[child]
predecessor[child]=vertex
minDistance[child]=ctr
unvisitedVertices.push(child)
return minDistance
```

To get the path we can recursively call the predecessor to print out the optimal path like,

```
printPath(dest, src)
print(dest)
if dest==src
return
printPath(predecessor[dest], src)
```

## Applications

- Dijkstra's Algorithm is widely used in
**networking**to determine the best way to move packets to a node. In fact, it is widely used in**routers**to send packets over the internet. - It is widely used in
**navigation systems**to find the shortest distance between two places. **Robots**use this algorithm to find the path between two places.- It is also used in
**social networking sites**to find the relationship between two individuals.

Dijkstra's Algorithm is a clean and simple algorithm based on a greedy approach. However it has it's limitations. Dijkstra's Algorithm is not a suitable algorithm for graphs with negative edges. But, fortunately, rarely we encounter situations in a practical scenario where a negative edge conveys a meaning that is relevant to the problem. And if a situation like that arises we have other algorithms, which we will look further down the line, which are apt for them.