c# - 源和目标相同时的 Dijkstra 算法示例

Question

给定以下有向加权图，如何找到起点和终点都在 B 的最短路线？

我正在尝试 Dijkstra，路径存在和不存在的情况都运行良好，但找不到一个例子来涵盖我上面问的情况。

到目前为止，这是我的代码

public static int ShortestDistance(Graph graph, Node from, Node to)
{
    var distances = new Dictionary<Node, int>();
    var actualNodes = graph.GetNodes() as List<Node> ?? Graph.GetNodes().ToList();

    foreach (var node in actualNodes) distances[node] = node.Equals(from) ? 0 : int.MaxValue;

    while (actualNodes.Count() != 0)
    {
        var actualShortest = actualNodes.OrderBy(n => distances[n]).First();
        actualNodes.Remove(actualShortest);

        if (distances[actualShortest] == int.MaxValue) break;

        if (actualShortest.Equals(to)) return distances[actualShortest];

        foreach (var adjacent in graph.GetAdjacentsByNode(actualShortest))
        {
            var actualDistance = distances[actualShortest] + adjacent.Weight;
            if (actualDistance >= distances[adjacent.To]) continue;
            distances[adjacent.To] = actualDistance;
        }
    }

    throw new Exception($"There's no such route from '{from}' to '{to}'.");
}

Answer 1

如果允许零长度路由:

• 那么答案就是0。

如果按路线，您指的是长度 > 0 的路径:

• 从源代码运行 Dijkstra，获取数组 sp[]，这样 sp[x] 存储从源到 x 的最短路径(这是 Dijkstra 的常规用法)

• 现在考虑所有传入源的边。

• 假设边是 x -> 源，权重为 w

• 因此我们可以到达路径 > 0 长度且总重量为sp[x] + w

• 从所有这些 route 选择最少的一条。