Dijkstra’s Shortest Path Algorithm

Implementation of Dijkstra’s algorithm and printing shortest path


Category: Data Structure And Algorithms Tags: C#

Dijkstra 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 with Cycle Implementation
Fig 1: Directed Graph with Cycle Implementation

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. Now we will create class for Vertex.

public class Vertex
{
    public string Name { get; set; }
    public int D { get; set; }
    public Vertex Parent { get; set; }
}

We will reuse same methods "InitializeSingleSource" and "Relax" from Bellman-Ford’s algorithm.  

public static void InitializeSingleSource(Vertex[] vertices, Vertex s)
{
    foreach (Vertex v in vertices)
    {
        v.D = int.MaxValue;
        v.Parent = null;
    }
    s.D = 0;
}
public static void Relax(Vertex u, Vertex v, int weight) { if (v.D > u.D + weight) { v.D = u.D + weight; v.Parent = u; } }

Now Let’s implement Dijkstra’s algorithm:

public static List<Vertex> Dijkstra(Vertex[] vertices, int[][] graph, int source)
{
    InitializeSingleSource(vertices, vertices[source]);
    List<Vertex> result = new List<Vertex>();
    //adding all vertex to priority queue
    PriorityQueue.PriorityQueue<Vertex> queue = new PriorityQueue.PriorityQueue<Vertex>(true);
    for (int i = 0; i < vertices.Length; i++)
        queue.Enqueue(vertices[i].D, vertices[i]);

    //treversing to all vertices
    while (queue.Count > 0)
    {
        var u = queue.Dequeue();
        result.Add(u);
        //again traversing to all vertices
        for (int v = 0; v < graph[Convert.ToInt32(u.Name)].Length; v++)
        {
            if (graph[Convert.ToInt32(u.Name)][v] > 0)
            {
                Relax(u, vertices[v], graph[Convert.ToInt32(u.Name)][v]);
                //updating priority value since distance is changed
                queue.UpdatePriority(vertices[v], vertices[v].D);
            }
        }
    }
    return result;
}

Let’s implement method to print the shortest path

public static void PrintPath(Vertex u, Vertex v, List<Vertex> vertices)
{
    if (v != u)
    {
        PrintPath(u, v.Parent, vertices);
        Console.WriteLine("Vertax {0} weight: {1}", v.Name, v.D);
    }
    else
        Console.WriteLine("Vertax {0} weight: {1}", v.Name, v.D);
}

Running above code:

static void Main(string[] args)
{
    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 } };
    Vertex[] vertices = new Vertex[adjacencyMatrix.GetLength(0)];
    //Source vertex
    int source = 0;

    for (int i = 0; i < vertices.Length; i++)
        vertices[i] = new Vertex() { Name = i.ToString() };
    //calling dijkstra  algorithm
    List<Vertex> result = Dijkstra(vertices, adjacencyMatrix, source);
    //printing distance
    PrintPath(vertices[0], vertices[2], result);
    Console.ReadLine();
}

Output:

Vertax 0 weight: 0

Vertax 3 weight: 3

Vertax 2 weight: 6


Like 0 People
Last modified on 22 March 2019
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 133
Questions: 9
Given Best Solutions: 9 *

Comments:

No Comments Yet

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

Existing User

Login via:

New User



x