Dijkstra 没有找到正确的路径

Question

我已经实现了 Dijkstra 算法来在无向加权图中找到最大权重路径。不幸的是，它 return 并非在所有情况下都是最佳路径。感谢任何帮助弄清楚我做错了什么。我盯着这段代码看了太久了。

        graph.AddConnection("A", "B", .5);
        graph.AddConnection("A", "J", .2);
        graph.AddConnection("A", "F", .63);
        graph.AddConnection("A", "Z", .92);
        graph.AddConnection("B", "C", .7);
        graph.AddConnection("B", "E", .112);
        graph.AddConnection("C", "D", .1);
        graph.AddConnection("F", "G", .21);
        graph.AddConnection("G", "D", .92);
        graph.AddConnection("J", "G", .56);
        graph.AddConnection("Z", "D", 0.99);

我试图找到从 A 到 G 的最强路径，它应该是：阿兹达格。相反，它正在输出 AFG。

private void ProcessGraph(Graph graph, string startingNode)
{
    bool finished = false;
    var queue = graph.Nodes.Values.ToList();
    while (!finished)
    {
        Node nextNode = queue.OrderBy(n => n.DistanceFromStart).FirstOrDefault(
        n => !double.IsPositiveInfinity(n.DistanceFromStart));
        if (nextNode != null)
        {
            var connections = node.Connections.Where(c => queue.Contains(c.Target));
            foreach (var connection in connections)
            {
              double distance = node.DistanceFromStart + connection.Distance;
              if (distance < connection.Target.DistanceFromStart)
                  connection.Target.DistanceFromStart = distance;
            }
            queue.Remove(nextNode);
        }
        else
        {
            finished = true;
        }
    }
}

编辑：权重限制为 0 < w < 1。

编辑 2：如果有人看到这个并犯了和我一样的错误：我刚刚意识到我是按递增顺序而不是递减顺序排列邻居的权重，这就是我的路径不正确的原因。我改为：

queue.OrderByDescending(n => n.DistanceFromStart).FirstOrDefault(
        n => !double.IsPositiveInfinity(n.DistanceFromStart));

并且算法按预期工作。

Answer 1

只需将所有权重 w 更改为 1.0 - w，Dijkstras 即可开箱即用。

将其转换为找到最大路径可能可行，但即使您可以修改算法使其可行，当您可以执行上述操作时，这些努力也是徒劳的。

Dijkstra 没有找到正确的路径

Dijkstra not finding correct path

c#

algorithm

dijkstra