Farruh Habibullaev
Personal Blog

Personal Blog

Practical Dijkstra’s Algorithm

Practical Dijkstra’s Algorithm

Farruh Habibullaev's photo
Farruh Habibullaev

Published on Nov 2, 2019

10 min read

Subscribe to my newsletter and never miss my upcoming articles

In computer science and discrete mathematics, we have encountered the concept of “single—source shortest path” many times. Dijkstra’s algorithm is one of the most popular algorithms for solving many single-source shortest path problems with non-negative edge weight in the graphs. However, we actually see rare use of the Dijkstra’s algorithm, or at least we are unaware of them. In this article, I will briefly explain how Dijkstra’s algorithm works. However, most parts of the article are devoted to showing case the practical use of the algorithm in different areas of computer science.

Note:

I assume the readers have prior knowledge of graph theory at least in discrete mathematics, and at least a little knowledge of algorithm design.

Introduction

Dijkstra’s algorithm is mainly used to find the shortest path from a starting node/point to the target node/point in a weighted graph. When Dijkstra’s algorithm is applied, it creates a tree of the shortest path from a starting vertex/source to all the other nodes in the graph. A few constraints for the application of Dijkstra’s algorithm, the graph must be a weighted graph with non-negative weighted edges. It can be either a directed or undirected graph.

A little insight into the algorithm with a simple example is that you may imagine you are planning to drive back from one state (California) to your state (Arizona), and definitely want to go thru the possible shortest path to minimize spending on petrol and save your time. Another example, you want to come back from school to home in the shortest possible way. You try to open a map service to look up the way, it is very likely map service engineers might have used Dijkstra’s algorithm and other algorithms to find the possible shortest path. In Dijkstra’s algorithm, that means it tries to find the shortest paths and build the shortest path tree by avoiding the edges/ways in our example with largest / longest weights as much as possible by a greedy approach.

Before we really dive into the details, please try to find the shortest path from home to school by a greedy approach in the given picture below. Please make sure your answer is correct and try to analyze and think about how you have come up with the solution.

Dijkstra’s Algorithm Details

Dijkstra’s algorithm finds the shortest path tree from a single-source node, by building a set of nodes that have a minimum distance from the source.

Graphs

The graph has the following properties:

  • vertices or nodes denoted by v or u

  • weighted edges that connect two nodes / vertices : (v, u) denotes the edge and w(v, u) denotes its weight. In the following examples, we have 6 vertices : a, f, c, b, e, d and we have weighted edge w(a, f) = 14 and so on.

General Overview

Actual implementation is usually done by initializing three values:

  • distances, an array of distances from the source node s to each node in the graph, initialized in the following way: the starting source node distances(s) = 0; and each of all the other nodes v distances(v) = infinity initialized at the beginning. The reason why all the other nodes are initialized with infinity at the beginning is as the algorithm proceeds, the distance from the source node s to each node v in the graph will be recalculated and finalized when the shortest distance to v is found.

  • Q, a queue of all the nodes in the graph. At the end of the algorithm process, Q will be empty.

  • S, an empty set, to indicate which nodes have visited. At the end of the algorithm’s run, S will have all the nodes of the graph.

Dijkstra’s Algorithm Procedure

The algorithm proceeds as following:

  1. While Q is not empty, pop the node v, that is not already in S, from Q with the smallest distances(v). In the first run, the source node s will be picked because distances(s) is initialized to 0. In the second run, the next node with the smallest distance value will be chosen.

  2. Add node v to Set s to indicate that v node has been visited when it is fully explored.

  3. Update each adjacent node u value of the node v according to the following rules: if distances(v) + weight(u, v) < distances(u), there is a new minimum distance found for u, so we need to update distance(u) to a new minimum value; otherwise, no update is needed.

Finally, Dijkstra’s algorithm has visited each node in the graph and found the smallest distance to each node from the source node, forming the shortest path tree. Below, I will first show the examples with an image for better understanding and visualization, then write a simple pseudo-code implementation.

Examples

Note : I have downloaded the image from the following source for reference.

a) As you can see, we are in the initial stages of the algorithm for finding the shortest path where s is initialized with 0 value and all the other nodes with infinity.

b) s node has two adjacent nodes t, y and the shortest path from s → t is weight(s, t) = 10 and from s -> y is weight(s, t) = 5 as for the following condition distances(v) + weight(u, v) < distances(u). And we update each adjacent node’s value accordingly. And now when the node s is fully explored, and we can add the node s to Set s.

c) Now we need to select the next shortest path node from the queue Q, and start exploring the adjacent nodes of that particular node. In our case, the shortest path node is the node y with value 5 and with adjacent nodes z, t, x. And we need to update each adjacent node value of node y according to the above-mentioned condition.

So, we have to iterate and select shortest path node u from the Queue Q, and check each of its adjacent nodes and update their values iteratively until Queue Q is empty as shown in d, e, f.

Pseudocode for the Dijkstra’s algorithm given below

func dijkstra(graph, source): // declaration of function, graph and source givenfor each vertex v in graph:
    Q <- v; //we need to initialize Q with all the vertices first
    distances[v] = infinity; //initialization of nodes with infinity value at first
  distances[source] = 0; // source must be initialized with 0 value, as it is source

while Q is not empty
  u <- minDistance(Q); // select the element with min distance value from Q it is source node initially
  remove u from Q;
  S <- S ∪{u}; // add u to the set of visited nodes;

   for each v ∈ neighbors[u] 
     if distances[v] > distances[u] + w(u,v); // if new shortest path found) then 
        d[v] <- d[u] + w(u, v);

return distances[];

In a very general and broad case, the time complexity is O(|E| + |V|²) and space complexity is O(|V|) for the algorithm. You can research more on edge cases and apply the Dijkstra algorithm for condensed graphs on your own.

If you are really into Dijkstra’s algorithm, you can try to solve interesting problems related to Dijkstra’s algorithm in Leetcode. I have listed a few of them here:

I have spent writing about the actual details of the algorithm Dijkstra more than I actually expected. I will focus on the practical application of Dijkstra’s algorithm in the real world from now onward.

Application of Dijkstra’s Algorithm

Application of Dijkstra’s algorithm has been used widely in several different aspects of engineering since its first introduction by computer scientist Edsger W. Dijkstra in 1956.

Mapping

If you have ever tried to find distance or a path from one point/location to another point/destination, let us say from one city to another, or from your location to the nearest gas station, it is very likely that you have encountered shortest path problem. In math term, it is finding the shortest path between two points in the graph, for which the Dijkstra’s algorithm is very likely to be applicable.

Another example would be that the firefighter department wants to develop a system that finds the shortest distance between the closest firefighter department and the house being burnt to avoid the extra delay. Or logistics companies want to develop a system that finds the shortest distance between the warehouse and destinations to avoid extra spending and time. For such systems’ development, the Dijkstra’s algorithm is very applicable.

Social Networking Application

In many social networking applications, it is very common to suggest the lists of the friends that a particular user may know. How do you think many social media companies implement this feature efficiently, especially when the system has over a billion users. The standard Dijkstra algorithm can be applied using the shortest path between users measured in handshakes or connections between two users.

As far as I know, many social networking applications are based on six degrees of separation that is the distance measured in the number of handshakes between any two users and it is quite small. Even if the average number of friends for users is not big, the problem of finding the shortest paths between users is very complex from the view of algorithm complexity.

When the social networking graph is very small, you can use standard Dijkstra’s algorithm to find the shortest paths, and however, when the graph is becoming bigger and bigger, the standard algorithm takes a few several seconds to count and is very inefficient.

However, I believe that with a few minor tweaks of Dijkstra‘s algorithm, the shortest distance between any users in the social networking graph can be found very efficiently. I won’t go into details since it takes really long explanation. You can do research on your own. By the way, if you do research on it, I am sure it is going to be a very interesting research topic.

Telephone Network

In a telephone network, each line has a bandwidth, bw. We would like to route the phone call thru the highest bw. The bandwidth of the transmission line is the highest frequency that that line can support. Generally, if the frequency of the signal is higher in a certain line, the signal is reduced by that line. If we are transmitted a digital signal then the bw represents the highest frequency or the fastest the signal can change from 0 to 0. Bandwidth represents the amount of information that can be transmitted by the line.

You may wonder how the algorithm can be applied to this problem. If we imagine a city to be a graph, the vertices represent the switching stations, and the edges represent the transmission lines and the weight of the edges represents bw. So as you can see it can fall into the category of shortest distance problem, for which the Dijkstra is very applicable.

Flight Agenda

A travel agent requests software for making an agenda of flights for clients. The agent has access to a database with all airports and flights. Besides the flight number, origin airport, and destination, the flights have departure and arrival times. Specifically, the agent wants to determine the earliest arrival time for the destination given an origin airport and start time.

Here we can assume that graph is a directed graph with certain directions. The vertices represent the airports, and directed edges represent edges with two weights, departure time and arrival time. With a slight modification of the Dijkstra algorithm, the solution can easily be found.

In the practical world, we can find many different practical applications of the Dijkstra algorithm, I have mentioned only a few of them here. I would like to stop giving the long list here since it is getting a little bit boring. In the next article in a few days, I am planning to go deep into the implementation of the Flight Agenda application using Dijkstra’s algorithm.

Thank you so much for reading, and I hope you learned at least a little bit of the usefulness of Dijkstra’s algorithm, and where it can be applied.

All the best,

 
Share this