# Implementation of Dijkstra’s algorithm and printing shortest path

 Category: Data Structure And Algorithms Tags: Dijkstra’s Shortest Path Algorithm - Code Files

Another single source shortest path algorithm is Dijkstra’s shortest path algorithm. We learned Bellman-Ford’s algorithm which runs on O (V.E) but well implemented Dijkstra’s algorithm can run on lower running time than Bellman-Ford’s algorithm, only limitation is all the edges should have positive weights.

## Implementation

We have to use priority queue which have learned in previous article, we reuse same code by adding reference of priority queue project in current project. We will reuse same method Relax from Bellman-Ford’s algorithm.

```static void Relax(int u, int v, int weight, int[] distance, int[] parent)
{
if (distance[u] != int.MaxValue && distance[v] > distance[u] + weight)
{
distance[v] = distance[u] + weight;
parent[v] = u;
}
}```

Now Let’s implement Dijkstra’s algorithm:

```public static void Dijkstra(int[][] adjacencyMatrix, int numberOfVertex, int[] distance, int[] parent)
{
PriorityQueue.PriorityQueue<int> vertexQueue = new PriorityQueue.PriorityQueue<int>(true);
//adding all vertex to priority queue
for (int i = 0; i < numberOfVertex; i++)
vertexQueue.Enqueue(distance[i], i); // priority = distance, object = vertex

//treversing to all vertices
while (vertexQueue.Count > 0)
{
var u = vertexQueue.Dequeue(); // vertax with least distance
//Traversing to all connecting edges
for (int v = 0; v < adjacencyMatrix[u].Length; v++)
{
{
//updating priority value since distance is changed
vertexQueue.UpdatePriority(v, distance[v]);
}
}
}
}```

Let’s implement method to print the shortest path

```public static void PrintPath(int u, int v, int[] distance, int[] parent)
{
if (v < 0 || u < 0)
{
return;
}
if (v != u)
{
PrintPath(u, parent[v], distance, parent);
Console.WriteLine("Vertax {0} weight: {1}", v, distance[v]);
}
else
Console.WriteLine("Vertax {0} weight: {1}", v, distance[v]);
}```

Running above code:

```static void Main(string[] args)
{
//Source vertex
int source = 0;
int[][] adjacencyMatrix = new int[][] { new int[] { 0,0,0,3,12 },
new int[] { 0,0,2,0,0 },
new int[] { 0,0,0,2,0 },
new int[] { 0,5,3,0,0 },
new int[] { 0,0,7,0,0 } };

int[] distance = Enumerable.Repeat(int.MaxValue, numberOfVertex).ToArray();
int[] parent = Enumerable.Repeat(-1, numberOfVertex).ToArray();
distance[source] = 0;
//calling dijkstra  algorithm
//printing distance
PrintPath(0, 2, distance, parent);
}```

Output:

Vertax 0 weight: 0

Vertax 3 weight: 3

Vertax 2 weight: 6

 Like 2 People Nikhil Joshi Ceo & Founder at Dotnetlovers Atricles: 158 Questions: 16 Given Best Solutions: 16 * `v.D > u.D + weight will result in integer overflow when u.D is int.Max and weight > 0`
Like 1 Person on 20 February 2021 Thanks unal,

Will look into it.

Like 1 Person on 20 February 2021 We have fixed the issue. Thanks for the feedback Unal.

Like 0 People on 9 March 2022

Login via:   x 