使用Dijkstra算法寻找最短路径

Question

我需要找到图的两个顶点之间的最短路径。我有一个矩阵，其中包含所有权重。我该怎么做？目前，我有以下代码：

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

它可以工作，但是，我不知道如何让它找到最短路线，例如1和3之间，并返回像1=>4=>2=>3这样的路线。
预先感谢。

Answer 1

Djikstra 算法使用父数组来跟踪从开始到结束的最短路径。您将从parent[end] 开始并跟踪数组的条目，直到回到开始为止。

一些伪代码：

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

shortestPath.Reverse();

对于函数，您唯一需要担心的是传入的起始值和结束值是否是适当的值（例如，它们是否实际上代表图形中的顶点）。

Answer 2

到达目标顶点后，您可以使用父矩阵回溯到起始顶点的路径。就像（假设有一条从源到目的地的路径）：

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

注意：路径将以相反的顺序排列。

Answer 3

Dijkstra 算法在

C# 12

中使用

.NET 8

的完整示例。并使用

NUnit

进行测试。

要编写此示例的代码，您需要三个哈希表：

graph

、

costs

和

parents

。

编码：

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

测试一下：

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

参考：Aditya Bhargava 的Grokking 算法