c# - Dijkstra 没有找到正确的路径

Question

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

        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 即可开箱即用。

将其转换为寻找最大路径可能可行，但即使您可以修改算法使其可行，如果您可以执行上述操作，那么这些努力都是徒劳的。