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++) { if (adjacencyMatrix[u][v] > 0) { Relax(u, v, adjacencyMatrix[u][v], distance, parent); //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 numberOfVertex = adjacencyMatrix[0].Length; int[] distance = Enumerable.Repeat(int.MaxValue, numberOfVertex).ToArray(); int[] parent = Enumerable.Repeat(-1, numberOfVertex).ToArray(); distance[source] = 0; //calling dijkstra algorithm Dijkstra(adjacencyMatrix, numberOfVertex, distance, parent); //printing distance PrintPath(0, 2, distance, parent); Console.ReadLine(); }
Output:
Vertax 0 weight: 0
Vertax 3 weight: 3
Vertax 2 weight: 6
Comments:
Thanks unal,
Will look into it.
We have fixed the issue. Thanks for the feedback Unal.