Finding the shortest route using Dijkstra algorithm

Question

I need to find the shortest route between 2 vertices of a graph. I have a matrix, which contains all the weights. How can I do it? Currently, I have the following code:

private int[] Dijkstra(int start, int end)
    {
        bool[] done = new bool[8];
        int[] parent = new int[8];
        for (int i = 0; i < parent.Length; i++)
            parent[i] = -1;
        int[] distances = new int[8];
        for (int i = 0; i < distances.Length; i++)
            distances[i] = int.MaxValue;
        distances[start] = 0;
        int current = start;
        while (!done[current])
        {
            done[current] = true;
            for (int i = 0; i < 8; i++)
            {
                if (graph[current, i] != int.MaxValue)
                {
                    int dist = graph[current, i] + distances[current];
                    if (dist < distances[i])
                    {
                        distances[i] = dist;
                        parent[i] = current;
                    }
                }
            }
            int min = int.MaxValue;
            for (int i = 0; i < 8; i++)
            {
                if (distances[i] < min&&!done[i])
                {
                    current = i;
                    min = distances[i];
                }
            }
        }
        return parent;
    }

It works, but, however I don't know how to make it find the shortest route between, for example 1 and 3, and return the route like 1=>4=>2=>3.
Thanks in advance.

Cancel

Answer 1

Djikstra's Algorithm uses the parent array to track the shortest path from start to end. You'd start at parent[end] and follow the entries of the array until you got back to start.

Some pseudocode:

List<int> shortestPath = new List<int>();
int current = end;
while( current != start ) {
     shortestPath.Add( current );
     current = parent[current];
}

shortestPath.Reverse();

Only thing you worry have to worry about with your function is whether or not the start and end values passed in are appropriate values (whether or not they actually represent vertices in your graph, for example ).

Discontinuance

Answer 2

Once you reach the destination vertex you can backtrack the path to the starting vertex using the parent matrix. Something like (given there's a path from source to dest):

void backtrack(int source, int dest, vector<int> &path) 
{
   path.push_back(dest);

   for(int vertex = parent[dest]; vertex != source; vertex = parent[vertex])
     path.push_back(vertex);

   path.push_back(source);
}

Note: path will be in reverse order.

Chuckle

Answer 3

Complete example of Dijkstra’s algorithm using C# 12 in .NET 8. And using NUnit for testing.

To code this example, you’ll need three hash tables: graph, costs and parents:

And the algorithm you need to implement looks like this:

Now code it:

public static class DijkstraAlgorithm
{
    public static void FindShortestPath(Dictionary<string, Dictionary<string, int>> graph,
        Dictionary<string, int> costs,
        Dictionary<string, string?> parents)
    {
        // Store the visited nodes
        var visited = new HashSet<string>();

        var lowestCostUnvisitedNode = FindLowestCostUnvisitedNode(costs, visited);
        while (lowestCostUnvisitedNode != null)
        {
            var cost = costs[lowestCostUnvisitedNode];
            var neighbors = graph[lowestCostUnvisitedNode];

            foreach (var neighbor in neighbors)
            {
                // New cost to get to the neighbor of lowestCostUnvisitedNode
                var newCost = cost + neighbor.Value;
                if (newCost < costs[neighbor.Key])
                {
                    costs[neighbor.Key] = newCost;
                    parents[neighbor.Key] = lowestCostUnvisitedNode;
                }
            }

            visited.Add(lowestCostUnvisitedNode);
            lowestCostUnvisitedNode = FindLowestCostUnvisitedNode(costs, visited);
        }
    }
    
    private static string? FindLowestCostUnvisitedNode(Dictionary<string, int> costs, HashSet<string> visited)
    {
        return costs
            .Where(node => !visited.Contains(node.Key))
            .OrderBy(node => node.Value)
            // When .Where above returns empty collection, this will give default KeyValuePair: { Key = null, Value = 0 }
            .FirstOrDefault()
            .Key;
    }

    // Not necessary for the algorithm, just created to answer this question
    public static string ConstructFinalRoute(Dictionary<string, string?> parents)
    {
        var route = new List<string>();
        var currentNode = "Finish";

        // The loop will exit when currentNode becomes "Start". "Start" has no parent, so currentNode gets null
        while (currentNode != null)
        {
            route.Add(currentNode);
            currentNode = parents.GetValueOrDefault(currentNode);
        }

        route.Reverse();
        return string.Join("=>", route);
    }
}

And test it:

using NUnit.Framework;

public class DijkstraAlgorithmTests
{
    [Test]
    public void DijkstraAlgorithm_Finds_Shortest_Path()
    {
        // Arrange
        var costs = new Dictionary<string, int>
        {
            // Costs from "start" to:
            { "A", 6 },
            { "B", 2 },
            { "Finish", int.MaxValue }
        };

        // Store the neighbors and the cost for getting to that neighbor
        var graph = new Dictionary<string, Dictionary<string, int>>
        {
            ["Start"] = new() { { "A", 6 }, { "B", 2 } }, // For eg: Going from Start to A and B
            ["A"] = new() { { "Finish", 1 } },
            ["B"] = new() { { "A", 3 }, { "Finish", 5 } },
            ["Finish"] = new()
        };

        // Store the parents
        var parents = new Dictionary<string, string?>
        {
            { "A", "Start" },
            { "B", "Start" },
            { "Finish", null }
        };
        
        // Act
        DijkstraAlgorithm.FindShortestPath(graph, costs, parents);
        var finalRoute = DijkstraAlgorithm.ConstructFinalRoute(parents);
        
        // Assert
        Assert.That(costs["Finish"], Is.EqualTo(6));
        Assert.That(parents["A"], Is.EqualTo("B"));
        Assert.That(parents["B"], Is.EqualTo("Start"));
        Assert.That(parents["Finish"], Is.EqualTo("A"));
        Assert.That(finalRoute, Is.EqualTo("Start=>B=>A=>Finish"));
    }
}

Reference: Grokking Algorithms by Aditya Bhargava

Lylalyle