Shortest Path Algorithm| Dijkstra | Greedy

5 min readNov 26, 2022

Imagine Google maps, we might want to see how much time will it take to reach all the nearby malls from our home. Some routes take longer time than the others. Finding the shortest path comes into the picture when we want to see which mall will be the closest by time. So how can you find so?

This can be represented as a weighted graph and Dijkstra algorithm can help to find the shortest path from source node to all the other nodes in the graph very efficiently.
Here, each mall as well as our home can be vertices and each route connecting vertices can be considered as edges with the time being the weights.
It is a greedy algorithm and at each node, we try to find the next best path until we have exhausted all the nodes. Starting from source node, we do breadth first search on the connecting vertices and updates the path sum for those.

How Dijkstra works:

Let’s consider the below graph with u or source =1:

First, let’s start from “source vertex” 1and update the weights needed to reach all the other nodes from vertex 1 in an array, let’s call it d[]
The nodes which does not have direct edge from our source will be defined as infinity for now and the source node itself will be at 0.

We also mark the “source” node/vertex as Visited each time we are having new source vertices = visited = {1}

Then we take the minimum of all nodes weight from updated weights and this makes the source node for the next iteration.
Once we mark our new source node visited, we can update all the connecting nodes from the source on the below condition:

If u is source, v is destination node (consider all other nodes/vertices one by one) and w is the cost need for connecting u->v
and V is not visited

if (v not in visited) and (d[u]+ w < d[v]):
    d[v] = d[u] + w

Since node 2 is the next smallest weighted node which is not visited from the above table d[], the visited set will be { 1,2 } and the updated weights will look like:

After this, we again select the next smallest weighted node from the updated ones, and repeat the same process unless we have exhausted visiting all nodes.

For the above table d[] , we first update through node 3 and then node 4 at the end.

Note: To find the smallest of updated weights, we can use a Min Heap which does the operation in O(log n) time and so keep pushing new updated nodes and their weights into the heap.

At end of this process, we can simply see the shortest path of all nodes from the initial source node.

Shortest path for all node from source node 1

Limitations:

This algorithm may not work for graphs with negative weights. (Check Bellman-Ford Algorithm for negative weights here)

When to use?

When the graph is directed. If undirected graph, we can consider two sided edges from the nodes to make it directed graph.
When shortest path to reach all the nodes from a single source is required.
When all the weights are positives.

Steps in detail:

Convert the array representations to a graph with u: List Of [v,w]s
Define an array to store all the weights of nodes from source, calling it d[].
Keep Visited Set to mark the visited ones — visited.
Keep a heap to find the minimum weighted node from the last updated weights — minHeap()
Perform Dijkstra algorithm.

Pop the least weighted node from heap, calling it uand mark it visited.
Iterate over all the connected nodes and their weights of u vertex, calling it v,w
If v is not visited already, check for the condition of d[v] update and update the d[v].
Push the new weight for v along with its vertex name.
Repeat the steps until heap is empty.

Code Snippet:

from math import inf
from heapq import heappop,heappush,heapify
from collections import defaultdict

def shortest_path(data,n,src):

    weights = defaultdict(list)
    for u,v,w in data:
        weights[u].append((w,v))
            
    visited =set()
    d = [inf]*(n+1) # since nodes are marked from 1 - 4
    d[src]=0  # since its the source node

    heap= [[0,src]]

    while len(heap):
        wu,u = heappop(heap)
        visited.add(u)
        
        if weights.get(u)==None: continue
        
        # update all the connected node weights
        for w,v in weights[u]:
            if v in visited: continue
            
            if d[u]+w < d[v]:
                d[v] = d[u]+w
                
                heappush(heap,[d[u]+w,v])
                
    print(f'The shortest path for all nodes from {src} \n>>  {d[1:]}') 
    # slicing since nodes are from [1,4]

### Calling the function
shortest_path([[1,2,1],[2,3,3],[1,3,5],[3,4,2]], 4, 1)

Time Complexity:

Since we are going over all the edges to find all the routes from one source, and each node can have E number of edges, we will have O(E)
Now for each step/loop, we are also trying to find the least weighted node via Min Heap whose time complexity for push and pop will be O(log V)
Hence the worst complexity is : O(E logV)

Follow Up:
We are using visited set to keep track of nodes which we have already passed. Do we really need this? Can we use the same array d[] for the tracking purpose?
Hint: Array d[] will already keep lower values if we have visited the node previously.

Shortest Path Algorithm| Dijkstra | Greedy

How Dijkstra works:

Limitations:

Steps in detail:

Code Snippet:

Practice Problems:

Reference:

Written by Frozen Codes