Dijkstra's Algorithm

Introduction

The objective of our project is to find a path between two vertices (nodes that denote cities) in a graph such that the total sum of the weights (distance between two cities) of the edges is the lowest possible number. This problem could be solved easily using Breadth First Search (BFS) when each edge’s weight is equal to 1, but in our project, weights can take any positive integer value, because we are going to generate the weights randomly. To solve the problem, we'll instead use an algorithm called Dijkstra’s algorithm to find the shortest path between two graph nodes.

Dijkstra’s algorithm

Dijkstra’s algorithm solves the problem discussed above by giving the shortest paths to all possible destinations from a given source. This algorithm works on a weighted graph, with the condition that no weight is negative. The algorithm follows the steps listed below:

1. Initialize the distance array for all the vertices (nodes) to infinity except for the source vertex. We need to set the distance for the source vertex to 0. Each element in the distance array will be of type list and each list will consist of two values: the first denoting the distance to reach the node from the source node and the second denoting the index of the node to reach the