时间戳

首页 > 解决方案 > Dijkstra 的算法已修改 - 在边缘上迭代？

algorithm - Dijkstra 的算法已修改 - 在边缘上迭代？

问题描述

我一直在考虑对 Dijkstra 算法进行修改，以消除对松弛步骤的需要。我可以得到人们的意见或为什么这不起作用的原因吗？我的实现以边缘优先级队列为中心，而不是节点。这是我的实现的描述：

我们有一个Graph有Node, 和子类的有向Edge类。 Edges有一个“权重”、一个“开始”节点和一个“结束”节点。 Nodes有一个“ dist ”值（用到达它们的最佳距离更新），以及一个“ bestPath ”值（用到达它们的最佳路径更新），最后是一个“ edges ”列表。

Dikstra (Node origin, Node goal):
    Set settledNodes = {}
    origin.dist = 0
    settledNodes.add(origin)

    Comparator<Edge, Edge> comparator = (edge1, edge2) -> 
        compareDoubles(edge1.weight + edge1.start.dist, edge2.weight + edge2.start.dist)

    PriorityQueue<Edge> queue = new PriorityQueue<>(comparator)
    queue.addAll(origin.edges)

    while (!queue.Empty || settledNodes.size < Graph.size):
        currEdge = queue.pop()

        if (!settledNodes.contains(currEdge.end)):
            currEdge.end.bestPath = currEdge

            if (currEdge.end == goal):
               return

            currEdge.end.dist = currEdge.weight + currEdge.start.dist
            queue.add(currEdge.end.edges)
            settledNodes.add(currEdge.end)

算法完成后，每个节点都将填充其“bestPath”字段，其中包含到达该节点要遵循的最佳边。可以回溯这些边缘以重新创建整个路径。

我意识到我的伪代码是 python 和 java 的邪恶结合——很抱歉。

这里的方法围绕迭代边缘的优先级队列而不是节点的列表/优先级队列。人们怎么想？据我所知，它仍然是最佳的，而且在我看来，这种算法在某些方面更好。例如，它不一定遍历它遇到的节点的所有边（与 Dijkstra 不同）。它通过将长边扔到优先级队列的底部来忽略它们，并且它可能会在不处理此类节点的情况下找到最佳路线，从而节省一些（或许多！）迭代。

我对这个算法非常兴奋，但是我在网上的任何地方都找不到这样的东西，这让我觉得我忽略了一些深层缺陷。我很想听听人们的反馈。

标签： algorithmgraphpathshortest-pathdijkstra

解决方案

您建议在折线图上运行 Dijkstra 。我相信这会奏效；但是请注意，Dijkstra 的渐近运行时间是 O((|E| + |V|) log|V|)。通过使用折线图，您实际上是在那里交换 E 和 V，从而使运行时间变差。

推荐阅读