Dijkstra：寻找目的地时如何设置终止条件？

Question

正如我们所知，Dijkstra 寻找从单个源节点到给定图中任何其他节点的最短路径。我尝试修改原始 Dijkstra 以找到一对源节点和目标节点之间的最短路径。只设置一个终止条件，在Dijkstra找到目的节点时终止程序，这看起来很简单。 但是，我在 Python 代码中设置的“终止条件”似乎导致了次优的最短路径，而不是最优的最短路径。 Dijkstra代码如下，

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)

邻接表的图形如图所示：

我想求从节点1到节点4的路径，有3条路径：

 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 将 select 路径 3: 1 --> 3 --> 4 因为它具有最小成本。

但是，我修改了终止条件，即当找到当前节点的邻接节点为目的地时，程序结束。并且我得到了节点1和节点4之间的一条路径的结果。结果是路径1：1 --> 2 --> 4。我分析了一下，这是因为我设置了错误的终止条件。当发现当前节点的邻接节点是目标时，程序将终止，这是错误的，但我不知道当目标节点是时设置适当的终止条件found.Could请你提供一些想法？

Answer 1

您的代码中实际上有正确的退出条件，即 current==sink。您不能强加任何其他退出条件。该算法必然需要运行直到访问到目标节点，因为只有此时您才能确定到目标的最短路径的值。由于这个条件，寻找单源单目的地最短路径的复杂性与寻找单源所有节点最短路径的复杂性相同。所以你的提前退出条件是正确的，你应该删除所有的邻居条件检查。

Answer 2

终止条件的唯一正确位置是刚从堆中获取当前节点时的外循环开始处。

当你迭代邻居时做那个测试是错误的，因为你不能保证最后一条边是最短路径的一部分。想象一下到邻居的最后一步的一些疯狂的高成本：那永远不会在最短路径上，所以不要在那里执行终止条件：仍然可能有另一条更便宜的到达接收器的路径。

我也没有看到您在代码中实际填充 parent 的位置。

我也不会从一开始就将所有节点都放在堆上，因为当元素较少时堆会更快。您可以从只有 1 个节点的堆开始。

另一个小优化是使用 parent 也将节点标记为已访问，因此您实际上并不需要 parent 和 visited。

最后，我不知道FibonacciHeap库，所以我只是采取了heapq，这是一个非常轻量级的堆实现：

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：寻找目的地时如何设置终止条件？

Dijkstra: how to set a termination condition when finding the destination?

algorithm

shortest-path

dijkstra