Shortest Path In Graph – Dijkstra’s Algorithm – C# Implementation

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
using System;
using System.Collections.Generic;
using System.Linq;
 
public static class DijkstraWithoutQueue
{
    public static List<int> DijkstraAlgorithm(int[,] graph, int sourceNode, int destinationNode)
    {
        var n = graph.GetLength(0);
 
        var distance = new int[n];
        for (int i = 0; i < n; i++)
        {
            distance[i] = int.MaxValue;
        }
 
        distance[sourceNode] = 0;
 
        var used = new bool[n];
        var previous = new int?[n];
 
        while (true)
        {
            var minDistance = int.MaxValue;
            var minNode = 0;
            for (int i = 0; i < n; i++)
            {
                if (!used[i] && minDistance > distance[i])
                {
                    minDistance = distance[i];
                    minNode = i;
                }
            }
 
            if (minDistance == int.MaxValue)
            {
                break;
            }
 
            used[minNode] = true;
 
            for (int i = 0; i < n; i++)
            {
                if (graph[minNode, i] > 0)
                {
                    var shortestToMinNode = distance[minNode];
                    var distanceToNextNode = graph[minNode, i];
 
                    var totalDistance = shortestToMinNode + distanceToNextNode;
 
                    if (totalDistance < distance[i])
                    {
                        distance[i] = totalDistance;
                        previous[i] = minNode;
                    }
                }
            }
        }
 
        if (distance[destinationNode] == int.MaxValue)
        {
            return null;
        }
 
        var path = new LinkedList<int>();
        int? currentNode = destinationNode;
        while (currentNode != null)
        {
            path.AddFirst(currentNode.Value);
            currentNode = previous[currentNode.Value];
        }
 
        return path.ToList();
    }
 
    public static void Main()
    {
        var graph = new[,]
        {
            // 0   1   2   3   4   5   6   7   8   9  10  11
            { 0,  0,  0,  0,  0,  0, 10,  0, 12,  0,  0,  0 }, // 0
            { 0,  0,  0,  0, 20,  0,  0, 26,  0,  5,  0,  6 }, // 1
            { 0,  0,  0,  0,  0,  0,  0, 15, 14,  0,  0,  9 }, // 2
            { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7,  0 }, // 3
            { 0, 20,  0,  0,  0,  5, 17,  0,  0,  0,  0, 11 }, // 4
            { 0,  0,  0,  0,  5,  0,  6,  0,  3,  0,  0, 33 }, // 5
            {10,  0,  0,  0, 17,  6,  0,  0,  0,  0,  0,  0 }, // 6
            { 0, 26, 15,  0,  0,  0,  0,  0,  0,  3,  0, 20 }, // 7
            {12,  0, 14,  0,  0,  3,  0,  0,  0,  0,  0,  0 }, // 8
            { 0,  5,  0,  0,  0,  0,  0,  3,  0,  0,  0,  0 }, // 9
            { 0,  0,  0,  7,  0,  0,  0,  0,  0,  0,  0,  0 }, // 10
            { 0,  6,  9,  0, 11, 33,  0, 20,  0,  0,  0,  0 }, // 11
        };
 
        PrintPath(graph, 0, 9);
        PrintPath(graph, 0, 2);
        PrintPath(graph, 0, 10);
        PrintPath(graph, 0, 11);
        PrintPath(graph, 0, 1);
    }
 
    public static void PrintPath(int[,] graph, int sourceNode, int destinationNode)
    {
        Console.Write(
            "Shortest path [{0} -> {1}]: ",
            sourceNode,
            destinationNode);
 
        var path = DijkstraWithoutQueue.DijkstraAlgorithm(graph, sourceNode, destinationNode);
 
        if (path == null)
        {
            Console.WriteLine("no path");
        }
        else
        {
            int pathLength = 0;
            for (int i = 0; i < path.Count - 1; i++)
            {
                pathLength += graph[path[i], path[i + 1]];
            }
 
            var formattedPath = string.Join("->", path);
            Console.WriteLine("{0} (length {1})", formattedPath, pathLength);
        }
    }
}