Dijkstra’s Algorithm in Python & C++ (Example)

What is the Shortest Path or Shortest Distance?

A path from the source vertex to the destination vertex that costs a minimum is the shortest path or shortest distance. In graph theory, it is possible to have multiple routes from a source to a destination. Among these routes, if there is a route that costs a minimum amount, we call it the shortest path.

Here “cost” means the number of nodes in the route or the summation of costs on each edge. A path can have one or multiple edges. The connection between two vertices is called an “edge”. There are various types of shortest path algorithms, such as Dijkstra’s Algorithm and the Bellman-Ford Algorithm.

Here, we discuss Dijkstra’s Algorithm. Let us look at the following weighted graph:

A Undirected-Weighted Graph

• The term “weighted” means the cost of moving from one node to another. For example, moving from node 1 to node 2, the cost or weight is 1.
• The path between node 1 and node 2 is called the edge.
• “Undirected” means you can move from one node to another and back to the previous node. So, if we try to find all the routes from node 1 to node 7, they will be:

Among these four routes, we can see that the first route costs 7. So, it is the shortest path in terms of cost.

Shortest Path

How Dijkstra’s Algorithm Works

Dijkstra’s Algorithm can find the shortest distance in both directed and undirected weighted graphs. This algorithm is greedy because it always chooses the shortest or closest node from the origin. The term “greedy” means that among a set of outcomes or results, the algorithm will choose the best of them.

Here, we are trying to find the shortest paths among all other routes. So, Dijkstra’s Algorithm finds all the shortest paths from a single source node. As a result, it behaves like a greedy algorithm.

In the “example” section below, you will see the step-by-step approach. It works as follows:

Step 1) Initialize the starting node with 0 cost and the rest of the nodes with infinity cost.
Step 2) Maintain an array or list to keep track of the visited nodes.
Step 3) Update the node cost with the minimum cost. It can be done by comparing the current cost with the path cost (demonstrated in the example section).
Step 4) Continue step 3 until all the nodes are visited.

After completing all these steps, we will find the path that costs a minimum from source to destination.

Difference Between Dijkstra and BFS, DFS

The main difference between Dijkstra and BFS-DFS is that Dijkstra is a shortest path-finding algorithm, while BFS and DFS are general path-finding algorithms. In general cases, BFS and DFS do not consider edge cost while finding the path. So, these algorithms cannot guarantee the shortest path.

2D Grid Demonstration of How BFS Works

Algosketch, showing BFS demonstration

This demonstration indicates that BFS only finds the path. However, it does not care about the path’s weight. BFS (Breadth-First Search) assumes that traveling from one node to another node will cost only 1.

Let us see an example graph:

Here, BFS finds a path in level 2. BFS traverses the graph in level order. So, it travels like this:

Step 1) Start from node “1” and visit all the adjacent nodes 2, 3, 4.

Step 2) Mark nodes 2, 3, 4 as level 1 and visit their adjacent nodes. It will continue exploring all the adjacent nodes until it reaches the destination node.

In terms of DFS, it will traverse the path from 1 to 7 like the following:

• 1→2→3→7 (Original Cost 10, DFS cost 3)
• 1→2→6→7 (Original Cost 7, DFS cost 3)
• 1→3→7 (Original Cost 8, DFS cost 2)
• 1→4→5→7 (Original Cost 13, DFS cost 3)

As we see, DFS calculates its path cost with the number of edges. DFS does the following:

• DFS can find a path from source (starting vertex) to destination.
• It cannot guarantee whether the path discovered from source node to destination is the shortest path or not.

However, in terms of Dijkstra’s Algorithm, it chooses edges based on their cost. As a greedy algorithm, it will pick the minimum cost paths.

Example of Dijkstra’s Algorithm

Dijkstra’s Algorithm uses the cost or weight to calculate the total cost of the path.

The target of Dijkstra’s Algorithm is to minimize this total cost or weight. In the example shown above, we find the best paths from node 1 to node 7, then calculate all the costs.

In Dijkstra’s Algorithm, it will find the shortest paths by calculating weights. It will not search for all possible paths. Let us demonstrate Dijkstra’s Algorithm with an example. For example, you have been asked to find the shortest path from node 1 to 7.

For this process, steps are given below:

Step 1) Initialize the starting node cost to 0. Assign “Inf” to the rest of the nodes. It means no path exists between the source and the node, or the path is not visited yet.

Step 2) When you select node 1, it will be marked as visited. Then update all the adjacent neighbors of node 1. 2, 3, 4 are the neighboring nodes of node 1.

While updating a cost, we need to follow the procedure below:

We can update each node’s cost using the above formula. For example, we were at node 1, and we needed to update the cost of its adjacent nodes 2, 3, 4. After updating, the costs will look like this:

Step 3) For node “2”, neighbors are 6 and 3. We are updating the cost at “6” by comparing infinity (current value) with the cost of node 2 + path cost from 2 to 6. Simply put, node “6” will have the cost of 1+3 or 4.

Node 3 is a neighbor of node 2. However, we calculated its cost in the previous step, which was 7. Now, if our path is 1-2-3, node 3 will have a cost of 10. Path 1-2-3 will cost 10, while 1 to 3 will cost 7.

Step 4) For node 3, the neighboring node is 7. So, comparing the current value of node 7 with the path cost (7+1) or 8, we will update the cost of node 7. That is 8. So, we find a path from node 1 to node 7, and it is 1→3→7. The cost is 8.

Step 5) For node 4, we will update its adjacent node cost accordingly. So, node “5” will have an updated cost of 8. After step 4 and 5, it will look like this:

Now, the path 1-3-7 has the cost of 8 (previously). Node “7” was not marked visited because we can reach node “7” from node “6”. The path “1-2-6” had a cost of 4. So the path 1-2-6-7 will have the cost of 7.

As 7 < 8, the shortest path from source vertex “1” to destination vertex “7” will be 1-2-6-7, and the cost is 7. Previously it was 1-3-7, and the cost was 8. So, the final graph will look like this:

The edge marked with a black line is our shortest path from 1 to 7, and it will cost us 7.

Pseudo Code Dijkstra’s Algorithm

Here is the pseudo-code for Dijkstra’s Algorithm:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- U
  return distance, previous

C++ Implementation of Dijkstra’s Algorithm

To implement Dijkstra’s algorithm using C++, here is the code:

#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
  int min = INT_MAX;
  int min_index = INT_MAX;
  for (int i = 0; i < size; i++) {
    if (!visited[i] && distance[i] <= min) {
      min = distance[i];
      min_index = i;
    }
  }
  return min_index;
}
void printParentPath(int parent[], int i) {
  if (parent[i] == -1) {
    return;
  }
  printParentPath(parent, parent[i]);
  cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
  int distance[size];
  bool visited[size];
  int parent[size];
  for (int i = 0; i < size; i++) {
    parent[0] = -1;
    distance[i] = INT_MAX;
    visited[i] = false;
  }
  distance[source] = 0;
  for (int i = 0; i < size - 1; i++) {
    int U = minimumDistance(distance, visited);
    visited[U] = true;
    for (int j = 0; j < size; j++) {
      int curr_distance = distance[U] + graph[U][j];
      if (!visited[j] && graph[U][j] &&
          curr_distance < distance[j]) {
        parent[j] = U;
        distance[j] = curr_distance;
      }
    }
  }
  cout << "Vertex\t\tDistance\tPath" << endl;
  for (int i = 1; i < size; i++) {
    cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
         << source + 1 << " ";
    printParentPath(parent, i);
    cout << endl;
  }
}
int main() {
  int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
                           {7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
                           {0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
                           {0, 0, 0, 0, 5, 3, 0}};
  dijkstra(graph, 0);
}

Output:

Vertex     Distance        Path

1->2           1             1 2
1->3           7             1 3
1->4           6             1 4
1->5           8             1 4 5
1->6           4             1 2 6
1->7           7             1 2 6 7

Python Implementation of Dijkstra’s Algorithm

To implement Dijkstra’s algorithm using Python, here is the code:

num_of_vertex = 7
def minimumDistance(distance, visited):
    _min = 1e11
    min_index = 1e11
    for i in range(num_of_vertex):
        if not visited[i] and distance[i] <= _min:
            _min = distance[i]
            min_index = i
    return min_index

def printParentNode(parent, i):
    if parent[i] == -1:
        return
    printParentNode(parent, parent[i])
    print("{} ".format(i + 1), end="")

def dijkstra(graph, src):
    distance = list()
    visited = list()
    parent = list()
    for i in range(num_of_vertex):
        parent.append(-1)
        distance.append(1e11)
        visited.append(False)
    distance[src] = 0
    for i in range(num_of_vertex - 1):
        U = minimumDistance(distance, visited)
        visited[U] = True
        for j in range(num_of_vertex):
            curr_distance = distance[U] + graph[U][j]
            if not visited[j] and graph[U][j] and curr_distance < distance[j]:
                parent[j] = U
                distance[j] = curr_distance
    print("Vertex\t\tDistance\tPath")
    for i in range(num_of_vertex):
        print("{}->{}\t\t{}\t\t{} ".format(src + 1, i + 1, distance[i], src + 1), end="")
        printParentNode(parent, i)
        print("")

graph = [
    [0, 1, 7, 6, 0, 0, 0],
    [1, 0, 9, 0, 0, 3, 0],
    [7, 9, 0, 0, 0, 0, 1],
    [6, 0, 0, 0, 2, 0, 0],
    [0, 0, 0, 2, 0, 0, 0],
    [0, 3, 0, 0, 0, 0, 3],
    [0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)

Output:

Vertex     Distance        Path

1->1           0              1
1->2           1              1 2
1->3           7              1 3
1->4           6              1 4
1->5           8              1 4 5
1->6           4              1 2 6
1->7           7              1 2 6 7

We can see that the algorithm calculates the shortest distance from the source node.

Application of Dijkstra Algorithm

Dijkstra’s Algorithm has a large set of uses. Among those, it is widely used in the field of networking. Here are some real-life uses of Dijkstra’s Algorithm:

Dijkstra in Google Maps: This algorithm is the backbone for finding the shortest paths, as we can see from the code snippet output above.

Google does not use the simple Dijkstra algorithm. Instead, it uses a modified version. When you select a destination, it shows you multiple paths in Google Maps. Among these paths, some are sorted out for the user. These paths are selected based on “time”. So, “time” is an edge cost for the shortest path.

Dijkstra in IP Routing: IP routing is a networking terminology. It describes how your data packet is sent to the receiver via different paths. These paths consist of routers, servers, and other equipment. In IP routing, there are different types of protocols.

These protocols help the router find the shortest paths to send the data. One of the protocol names is “OSPF (Open Shortest Path First)”. OSPF uses Dijkstra’s algorithm. The router maintains a table of routes. Each router shares its table with neighbor routers. After receiving the updated table, they must calculate all the paths again. At that time, the router uses Dijkstra’s Algorithm.

Limitation of Dijkstra’s Algorithm

Dijkstra’s algorithm cannot guarantee the shortest path in a graph with negative edges. Dijkstra’s algorithm follows these principles:

• One shortest path will be taken from one node to another.
• Once the shortest path between two nodes is selected, it will not be calculated again.

Here, notice two examples with negative edges.

In the left graph, there are three vertices. Dijkstra will run on the graph like the following:

Step 1) Starting vertex “1” will be initialized to zero. The other nodes will have infinity.

Step 2) Mark node “1” as visited and include it in the shortest path.

Step 3) The distance of the source node 1 to nodes “2” and “3” is set to infinity, as the shortest path is yet to be calculated. So, any path that costs less than infinity will be added to the shortest path (greedy approach).

Step 4) Updating the distance from source vertex “1” to “2”. The current weight will be 5 (5 < infinity). Similarly, update the distance from node “1” to “3” with the weight of 3.

Step 5) Now if we check the shortest distances from node “1”, we find that 5 is the shortest distance for edge 1→2. So, node “2” will be marked as visited. Similarly, node “3” will also be marked as visited as the shortest distance is 3.

However, if we observe, there is a path 1-3-2 that will cost only 2. But Dijkstra shows that from node “1” to node “2”, the shortest distance is 5. So, Dijkstra failed to calculate the shortest distance correctly. The reason is that Dijkstra is a greedy algorithm. So, once a node is marked visited, it will not be reconsidered, although there might be a shorter path available. This issue only occurs when the edges have negative costs or negative weight edges.

Dijkstra fails to calculate the shortest path between two nodes in this scenario. As a result, this algorithm has some drawbacks. To solve this negative edge problem, another algorithm called the “Bellman-Ford Algorithm” is used. That algorithm can work with negative edges.

Dijkstra’s Algorithm Complexity

The implementation above used two “for” loops. These loops run for the number of vertices. So, the time complexity is O(V²). Here, the term “O” is a notation that gives an assumption for the Dijkstra algorithm.

We can store the graph using a “priority queue”. A priority queue is a binary heap data structure. It will be more efficient than a 2D matrix. An edge with a minimum cost will have a high priority. Then the time complexity will be O(E log V). Here, E is the number of edges, and V is the number of vertices.

The space complexity is O(V²), as we are using an adjacency matrix (2D array). Space complexity can be optimized using an adjacency list or queue data structure.

FAQs