Tag: shortest path in graph

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);
        }
    }
}