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 negative weights), V be the set of all vertices and 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|)

Running Dijkstra's Algorithm on a Tree with src=0
Running Dijkstra's Algorithm on a Tree with src=0

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.