源和目标相同时的 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
从所有这些路线中选择最少的一条。

Answer 2

执行此操作的规范方法是复制（或 "shadow"）节点 B（称之为 BB），具有相同的传入和传出边和权重。

现在，应用 Dijkstra 算法找到从 B 到 BB 的最短路径。您已经有了该代码（即 "We have now reduced the problem to something which has previously been solved"）。

Answer 3

将节点拆分为两个节点：

节点S保留所有出边
节点D保留所有传入边

现在正常求解 S 作为源和 D 作为目标。

Answer 4

您执行此算法的速度很慢，但它有效。如果你想搜索从一个节点到它自己的 >0 路径，你可以像这样改变你的初始化：

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] = int.MaxValue;

    foreach (var adjacent in graph.GetAdjacentsByNode(from))
    {
        distances[adjacent.To] = adjacent.Weight;
    }

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

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

Example of Dijkstra algorithm when source and destination are the same

c#

algorithm

dijkstra