Dijkstra’s Algorithm

7 min readMar 24, 2021

Introduction to Graphs

In order to understand an algorithm, we need to understand the context of it. Dijkstra’s Shortest Path Algorithm also needs a context for it to be explained. The concept being ‘graphs’.

Graphs are data structures that show “connections” between two or more items.

Nodes are the name for these elements. They are representations of real-world events, people, or entities. Edges are the links between nodes.

Graphs can be specifically applied to real-life situations. For example, we might model a transportation network using graphs, with nodes representing facilities that send or receive goods and edges representing roads or paths that link them.

Types of Graphs

Graphs can take the following forms:

Undirected: you could go from one node to another in both directions for any pairs of connected nodes.

Directed: you can only go from one connected node to the other in a particular direction for each and every pair of connected nodes. To depict directed edges, we use arrow rather than simple lines.

Purpose

A weight graph is a graph with “weighted” or “costed” edges. An edge’s weight may represent distance, time, or something else that represents the “relation” between the two nodes it connects.

The shortest path between the current location and the destination is found using this algorithm in GPS devices. It has a wide range of applications in industry, especially in domains that require network modelling.

Basics of Dijkstra’s Algorithm

Dijkstra’s Algorithm begins at the node you choose (the source node) and analyses the graph to determine the shortest path between that node and all other nodes in the graph.

The algorithm keeps track of the shortest distance between each node and the source node, and it updates these values if a shorter path is found.

When the algorithm has found the shortest path between two nodes, that node is marked as “visited” and added to the path.

The procedure is repeated until the path contains all of the nodes in the graph. As a result, we have a path that connects the source node to all other nodes, taking the shortest route possible to each node.

Only graphs with positive weights can be used by Dijkstra’s Algorithm. This is due to the fact that the weights of the edges must be applied during the process in order to find the shortest path.

Requirements

The algorithm will not work properly if the graph contains a negative weight. The current path to that node is marked as the shortest path to that node until it has been classified as “visited.” Negative weights, on the other hand, will change this if the total weight can be decreased after this step.

Example

We have this graph:

The algorithm can find the shortest path between node 0 and every other node in the graph.
For each node in the graph, we’ll find the shortest path from node 0 to node 1, node 0 to node 2, node 0 to node 3, and so on.

We begin with the following list of distances (please see the list below):

The distance between the source node and itself is 0 . The source node will be node 0 in this case, but it can be any node you want.
We use the infinity symbol to denote the distance from the source node to all other nodes since the distance has yet to be calculated.

We can label this node as visited since we chose to start at node 0. We cross it off the list of unvisited nodes and draw a red border around the corresponding node in the diagram:

Now we must check the distance between node 0 and its neighbouring nodes. These are nodes 1 and 2 (as shown by the red edges):

The distances from node 0 to node 1 and node 2 must be modified with the weights of the edges connecting them to node 0. (the source node). These are the corresponding weights of 2 and 6:

After we’ve updated the distances between nodes, we need to do the following:

Based on current known distances, choose the node that is nearest to the source node.

Make a note that it has been used.

Make a note of it and add it to your path.

We add node 1 to the path since it has the shortest distance to the source node (a distance of 2).

This is represented by a red edge in the diagram:

We mark it in the list with such a red square to show that it has been “visited” and that we have discovered the shortest way to it:

We cross it off from the list of unvisited nodes:

We must now evaluate the new neighbouring nodes in order to determine the shortest path to them. Just the nodes that are parallel to the nodes that are already part of the shortest path will be examined (the path marked with red edges).

Since they are directly connected to node 0 and node 1, respectively, nodes 3 and 2 are both neighboring to nodes already in the path, as shown below. These are the nodes we’ll look at in the next section.

We don’t need to change the distance from the source node to node 2 this time because we already have it clearly stated in our list. Only the distance from the source node to the new adjacent node (node 3) needs to be updated:

This distance is 7. We add the amounts of all the edges that form the shortest route to that node (in this case, node 3) to find the distance between the source node and another node (in this case, node 3):

Since we add the weight of the edges that shape the path 0 -> 1 -> 3 (2 for the edge 0 -> 1 and 5 for the edge 1 -> 3), the distance covered for node 3 is 7.

Now that we know how far apart the nodes are, we must determine which one will be added to the path. The unvisited node with the shortest (currently known) distance to the source node must be chosen.

We can instantly tell that this is node 2 with range 6 from the array of distances:

To find the shortest path from the source node to the new adjacent node, node 3, we must repeat the procedure.
As you can see, there are two options: 0 -> 1 -> 3 or 0 -> 2 -> 3. Let’s see if we can work out which direction is the shortest.

In the list, Node 3 already has a distance that was previously registered (7, see the list below). The weights 5 and 2 of the two edges that we needed to cross to follow the path 0 -> 1 -> 3 were added in a previous stage, resulting in this distance.

However, we now have another choice. If we select the direction 0 -> 2 -> 3, we must follow two edges 0 -> 2 and 2 -> 3 with weights of 6 and 8, respectively, covering a total distance of 14.

At the very end we will reach the shortest path: 0 -> 1 -> 3 -> 5 with a distance of 22.

Summary

Graphs are used to represent the relationships between things, persons, and entities. They are made up of two key components: nodes and edges. Objects are represented by nodes, and relations between them are represented by edges.
The shortest path between a given node (referred to as the “source node”) and all other nodes in a graph is determined by Dijkstra’s Algorithm.
This algorithm finds the path that minimises the total distance (weight) between the source node and all other nodes by using the edge weights.