我一直在考虑对Dijkstra算法进行修改，以消除对松弛步骤的需要。我能得到人们的意见或者为什么这行不通吗?我的实现以边的优先队列为中心，而不是以节点为中心。下面是我的实现的描述:
我们有一个有向Graph类，它有Node和Edge子类。Edges有">权值， a ">start";节点和">结束";节点。Nodes有">dist";值(以到达它们的最佳距离更新)，以及">bestPath";值(更新为到达它们的最优路径)，最后一个">边";列表。
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)
算法完成后，每个节点将拥有自己的"最佳路径"。字段填充，包含到达该节点要遵循的最佳边。为了重新创建整个路径，可以回溯这些边缘。
我意识到我的伪代码是python和java的邪恶混合-抱歉。
这里的方法围绕着边缘优先级队列而不是节点列表/优先级队列进行迭代。人们是怎么想的?据我所知，它仍然是最优的，在我看来，这个算法在某些方面更好。例如，它不必遍历遇到的节点的所有边(不像Dijkstra)。它通过将长边扔到优先级队列的底部来忽略它们，并且它可能在不处理这些节点的情况下找到最优路由，从而节省了一些(或许多!)迭代。
我对这个算法很兴奋，但是我在网上找不到这样的东西，这让我觉得我忽视了一些深刻的缺陷。我很乐意听到大家的反馈。
你建议在线形图上运行Dijkstra's。我相信这是可行的;但是请注意Dijkstra的渐近运行时间是O(((|E| + |V|) log|V|)。通过使用线形图，你实际上是在交换E和V，使运行时间更糟。