Dijkstra’s Shortest Path Algorithm

Implementation of Dijkstra’s algorithm and printing shortest path


Category: Data Structure And Algorithms Tags: C#

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.

Directed Graph
Fig 1: Directed Graph

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


Like 2 People
Last modified on 9 March 2022
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 164
Questions: 16
Given Best Solutions: 16 *

Comments:

unal
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
Nikhil Joshi

Thanks unal,

Will look into it.

Like 1 Person on 20 February 2021
Nikhil Joshi

We have fixed the issue. Thanks for the feedback Unal.

Like 0 People on 9 March 2022

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x