Dijkstra：寻找目的地时如何设置终止条件？ [英] Dijkstra: how to set a termination condition when finding the destination?
问题描述
众所周知，Dijkstra找到了从单个源节点到给定图中任何其他节点的最短路径。我尝试修改原始Dijkstra，以找到一对源节点和目标节点之间的最短路径。仅当Dijkstra找到目标节点时，才设置终止程序的终止条件似乎很容易。
但是，终止条件我在Python代码中设置的代码似乎导致了次优的最短路径，而不是最优的最短路径。
Dijkstra代码如下，
As we know, Dijkstra finds the shortest path from a single source node to any other node in a given graph. I try to modify the original Dijkstra to find the shortest path between a pair of the source node and destination node. It seems easy that only set a termination condition for terminating the program when the Dijkstra finds the destination node. However, the "termination condition" I set in my Python codes seems to lead a sub-optimal shortest path rather than the optimal shortest path. The Dijkstra code is as follows,
def dijkstra(adjList, source, sink):
#define variables
n = len(adjList) #intentionally 1 more than the number of vertices, keep the 0th entry free for convenience
visited = [False]*n
parent = [-1] *n
#distance = [float('inf')]*n
distance = [1e7]*n
heapNodes = [None]*n
heap = FibonacciHeap()
for i in range(1, n):
heapNodes[i] = heap.insert(1e7, i)
distance[source] = 0
heap.decrease_key(heapNodes[source], 0)
while heap.total_nodes:
current = heap.extract_min().value
#print("Current node is: ", current)
visited[current] = True
#early exit
if sink and current == sink:
break
for (neighbor, cost) in adjList[current]:
if not visited[neighbor]:
if distance[current] + cost < distance[neighbor]:
distance[neighbor] = distance[current] + cost
heap.decrease_key(heapNodes[neighbor], distance[neighbor])
if neighbor == sink and current != source: # this is a wrong logic , since the neighbor may not be selected as the next hop.
print("find the sink 1")
printSolution(source, sink, distance,parent)
break
if neighbor == sink:
print("find the sink2")
break
return distance
adjList = [
[],
[[2, 7], [3, 9], [6, 14]],
[[1, 7], [4, 15], [3, 10]],
[[1, 9], [2, 10], [4, 11], [6, 2]],
[[2, 15], [3, 11], [5, 6]],
[[4, 6], [6, 9]],
[[5, 9], [1, 14]]
]
dijkstra(adjList,1,4)
邻接表的图形如下所示：
The graph of the adjacency list is as shown:
我想找到从节点1到节点4的路径，有3条路径：
I want to find the path from node 1 to node 4, there are three paths:
path 1: 1 --> 2 --> 4 cost: 22
path 2: 1 --> 2 --> 3 --> 4 cost: 28
path 3: 1 --> 3 --> 4 cost: 20
path 4: 1 --> 3 --> 6 --> 5 --> 4 cost: 26
path 5: 1 --> 6 --> 3 --> 4 cost: 28
path 6: 1 --> 6 --> 5 --> 4 cost: 29
最初，Dijkstra将选择路径3：1-> 3-> 4，因为它具有最低的成本。
Originally, Dijkstra will select path 3: 1 --> 3 --> 4 since it has the minimum cost.
但是，我修改了终止条件，即当找到当前节点的邻接节点是目的地时，程序将结束。然后得到节点1和节点4之间的路径结果。结果为路径1：1->。 2-> 4.
我分析这是因为我设置了错误的终止条件。当发现当前节点的邻接节点是目标节点时，程序将终止，这是错误的，但是我不知道在找到目标节点时设置适当的终止条件。请提供一些想法吗？
But, I modify the termination condition, i.e., when finding the adjacency node of the current node is the destination, the program will be ended. And I get the result of a path between node 1 and node 4. The result is path 1: 1 --> 2 --> 4. I analyze that, this is because I set the wrong termination condition. The program will be terminated when finding the adjacency node of the current node is the destination, that is wrong but I have no idea that setting a proper termination condition when the destination node is found.Could you please provide some ideas?
推荐答案
唯一的终止条件是从堆中获取当前节点时在外循环的开始。
The only right place for the termination condition is at the start of the outer loop when you just got the current node from the heap.
在迭代邻居时执行该测试是错误的，因为您无法保证最后一条边是最短路径的一部分。试想一下，到邻居的最后一步会付出高昂的疯狂成本：永远不可能走在最短的路径上，所以不要在此处执行终止条件：可能还有另一条通往水槽的路径更便宜。
It is wrong to do that test when you iterate the neighbors, as you don't have the guarantee that this last edge is part of the shortest path. Just imagine some insane high cost for that last step to the neighbor: never could that be on the shortest path, so don't perform the terminating condition there: there still might be another path to the sink that is cheaper.
我也没有看到您的代码中实际填充了 parent 的位置。
I also did not see where you actually populated parent in your code.
我也不会放堆中的所有节点从一开始就开始，因为当堆中的元素较少时，它们会更快。您可以从只有1个节点的堆开始。
I would also not put all nodes on the heap from the start, as heaps are faster when they have fewer elements. You can start with a heap with just 1 node.
另一个小优化是使用 parent 还将节点标记为已访问，因此您实际上并不需要同时访问父母和 。
Another little optimisation is to use parent also for marking nodes as visited, so you don't actually need both parent and visited.
最后，我不知道 FibonacciHeap 库，所以我刚刚使用了 heapq ，这是一个非常轻便的堆实现：
Finally, I don't know the FibonacciHeap library, so I have just taken heapq, which is a very light heap implementation:
from heapq import heappop, heappush
def dijkstra(adjList, source, sink):
n = len(adjList)
parent = [None]*n
heap = [(0, source, 0)] # No need to push all nodes on the heap at the start
# only add the source to the heap
while heap:
distance, current, came_from = heappop(heap)
if parent[current] is not None: # skip if already visited
continue
parent[current] = came_from # this also marks the node as visited
if sink and current == sink: # only correct place to have terminating condition
# build path
path = [current]
while current != source:
current = parent[current]
path.append(current)
path.reverse()
return distance, path
for (neighbor, cost) in adjList[current]:
if parent[neighbor] is None: # not yet visited
heappush(heap, (distance + cost, neighbor, current))
adjList = [
[],
[[2, 7], [3, 9], [6, 14]],
[[1, 7], [4, 15], [3, 10]],
[[1, 9], [2, 10], [4, 11], [6, 2]],
[[2, 15], [3, 11], [5, 6]],
[[4, 6], [6, 9]],
[[5, 9], [1, 14]]
]
dist, path = dijkstra(adjList,1,4)
print("found shortest path {}, which has a distance of {}".format(path, dist))
这篇关于Dijkstra：寻找目的地时如何设置终止条件？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
