python上Dijkstra算法实现的断言错误

Question

我有一个python文件，在其中我迭代地实现了dijkstra的算法。图以邻接矩阵格式给出

问题是，在试块的最后一种情况下，这是预期结果：[13.0,10.0,14.0,0.0,6.0,7.0,8.0] 这就是我得到的结果：[13.0,10.0,18.0,0.0,6.0,7.0,8.0]

我在其余的案例中没有任何错误，这是我得到的唯一奇怪的案例

你知道这是为什么吗

代码如下：

from time import time
from math import inf
import math


# function to get the node with the minimum distance in shortest_path_list
# that hasn't been visited
def min_dist_node(graph, visited, sp_list, current_node):
    dist = inf
    node = 0
    for i in range(0, len(graph)):
        if i != current_node and not math.isinf(graph[current_node][i]) and dist > graph[current_node][i] and not visited[i]:
            dist = graph[current_node][i]
            node = i
    return node



# Dijkstra's algorithm
def Dijkstra (graph, initial):
    sp_list = []
    visited = [False]*len(graph)
    
    for node in range(0, len(graph)):
        sp_list.append(graph[initial][node])
        
    sp_list[initial] = 0.0
    visited[initial] = True
    current_node = initial
    
    while False in visited:
        current_node = min_dist_node(graph, visited, sp_list, current_node)
        visited[current_node] = True
        
        for node in range(0, len(graph)):
            if sp_list[node] > sp_list[current_node] + graph[current_node][node]:
                sp_list[node] = sp_list[current_node] + graph[current_node][node]
    return sp_list


    
    


def test():
   
    g0 =  [[0.0, 5.0, 1.0, inf],
          [5.0, 0.0, 1.0, 2.0],
          [1.0, 1.0, 0.0, 10.0],
          [inf, 2.0, 10.0, 0.0]]
    
    assert Dijkstra(g0, 3) == [4.0, 2.0, 3.0, 0.0]
 
    
    g1 =  [[0.0, 2.0],
           [2.0, 0.0]]
    
    assert Dijkstra(g1,0) == [0.0,2.0]

    
    g2 = [[0.0, 5.0, 3.0],
          [5.0, 0.0, inf],
          [3.0, inf, 0.0]]
    
    assert Dijkstra(g2, 1) == [5.0, 0.0, 8.0]

        
     
    g3 = [[0.0, 1.0, 2.0, 3.0, 4.0],
          [1.0, 0.0, inf, inf, 8.0],
          [2.0, inf, 0.0, 2.0, 2.0],
          [3.0, inf, 2.0, 0.0, 5.0],
          [4.0, 8.0, 2.0, 5.0, 0.0]]
    
    assert Dijkstra(g3, 3) == [3.0, 4.0, 2.0, 0.0, 4.0]

        
    g4 = [[0.0, 6.0, 2.0, 5.0],
          [6.0, 0.0, 4.0, inf],
          [2.0, 4.0, 0.0, 2.0],
          [5.0, inf, 2.0, 0.0]]
    
    assert Dijkstra(g4, 3) == [4.0, 6.0, 2.0, 0.0]
   
    
    g5 = [[0.0, 10.0, 1.0, inf, inf, inf],
          [10.0, 0.0, inf, 5.0, 4.0, inf],
          [1.0, inf, 0.0, 8.0, 2.0, 3.0],
          [inf, 5.0, 8.0, 0.0, inf, 2.0],
          [inf, 4.0, 2.0, inf, 0.0, inf],
          [inf, inf, 3.0, 2.0, inf, 0.0]]
    
    assert Dijkstra(g5, 0) == [0.0, 7.0, 1.0, 6.0, 3.0, 4.0]

    
    
    g6 = [[0.0, 3.0, 1.0, inf, inf, inf, inf],
          [3.0, 0.0, 8.0, 10.0, 5.0, inf, inf],
          [1.0, 8.0, 0.0, inf, inf, inf, inf],
          [inf, 10.0, inf, 0.0, 6.0, inf, 9.0],
          [inf, 5.0, inf, 6.0, 0.0, 1.0, 2.0],
          [inf, inf, inf, inf, 1.0, 0.0, 4.0],
          [inf,inf,inf, 9.0, 2.0, 4.0, 0.0]]
    
    print(Dijkstra(g6, 3))
    assert Dijkstra(g6, 3)  == [13.0, 10.0, 14.0, 0.0, 6.0, 7.0, 8.0]

start_time = time()
test()
elapsed_time = time() - start_time   
print("Elapsed time: %0.10f seconds." % elapsed_time)       

Answer 1

更新！我找到了一种不使用优先级队列的解决方法。如果我们将dist>；=图[初始] [i]我们首先考虑所有距离（从初始节点）不等INF，然后考虑所有的INF。p>

我认为这是正确的方法，如果有人看到一些错误，请告诉我

这就是所有算法现在的样子：

from time import time
from math import inf


# function to get the node with the minimum distance in shortest_path_list
# that hasn't been visited
def min_dist_node(graph, visited, sp_list, initial):
    dist = inf
    node = 0
    for i in range(0, len(graph)):
        if i != initial and dist >= graph[initial][i] and not visited[i]:
            dist = graph[initial][i]
            node = i
    return node


# Dijkstra's algorithm
def Dijkstra (graph, initial):
    sp_list = []
    visited = [False]*len(graph)
    
    for node in range(0, len(graph)):
        sp_list.append(graph[initial][node])
        
    visited[initial] = True
    
    while False in visited:
        current_node = min_dist_node(graph, visited, sp_list, initial)
        visited[current_node] = True
        
        for node in range(0, len(graph)):
            if sp_list[node] > sp_list[current_node] + graph[current_node][node]:
                sp_list[node] = sp_list[current_node] + graph[current_node][node]
    return sp_list


def test():
   
    g0 =  [[0.0, 5.0, 1.0, inf],
          [5.0, 0.0, 1.0, 2.0],
          [1.0, 1.0, 0.0, 10.0],
          [inf, 2.0, 10.0, 0.0]]
    
    assert Dijkstra(g0, 3) == [4.0, 2.0, 3.0, 0.0]
 
    
    g1 =  [[0.0, 2.0],
           [2.0, 0.0]]
    
    assert Dijkstra(g1,0) == [0.0,2.0]

    
    g2 = [[0.0, 5.0, 3.0],
          [5.0, 0.0, inf],
          [3.0, inf, 0.0]]
    
    assert Dijkstra(g2, 1) == [5.0, 0.0, 8.0]

        
     
    g3 = [[0.0, 1.0, 2.0, 3.0, 4.0],
          [1.0, 0.0, inf, inf, 8.0],
          [2.0, inf, 0.0, 2.0, 2.0],
          [3.0, inf, 2.0, 0.0, 5.0],
          [4.0, 8.0, 2.0, 5.0, 0.0]]
    
    assert Dijkstra(g3, 3) == [3.0, 4.0, 2.0, 0.0, 4.0]

        
    g4 = [[0.0, 6.0, 2.0, 5.0],
          [6.0, 0.0, 4.0, inf],
          [2.0, 4.0, 0.0, 2.0],
          [5.0, inf, 2.0, 0.0]]
    
    assert Dijkstra(g4, 3) == [4.0, 6.0, 2.0, 0.0]
   
    
    g5 = [[0.0, 10.0, 1.0, inf, inf, inf],
          [10.0, 0.0, inf, 5.0, 4.0, inf],
          [1.0, inf, 0.0, 8.0, 2.0, 3.0],
          [inf, 5.0, 8.0, 0.0, inf, 2.0],
          [inf, 4.0, 2.0, inf, 0.0, inf],
          [inf, inf, 3.0, 2.0, inf, 0.0]]
    
    assert Dijkstra(g5, 0) == [0.0, 7.0, 1.0, 6.0, 3.0, 4.0]

    
    
    g6 = [[0.0, 3.0, 1.0, inf, inf, inf, inf],
          [3.0, 0.0, 8.0, 10.0, 5.0, inf, inf],
          [1.0, 8.0, 0.0, inf, inf, inf, inf],
          [inf, 10.0, inf, 0.0, 6.0, inf, 9.0],
          [inf, 5.0, inf, 6.0, 0.0, 1.0, 2.0],
          [inf, inf, inf, inf, 1.0, 0.0, 4.0],
          [inf,inf,inf, 9.0, 2.0, 4.0, 0.0]]
    
    print(Dijkstra(g6, 3))
    assert Dijkstra(g6, 3)  == [13.0, 10.0, 14.0, 0.0, 6.0, 7.0, 8.0]

start_time = time()
test()
elapsed_time = time() - start_time   
print("Elapsed time: %0.10f seconds." % elapsed_time)

Answer 2

逻辑上似乎有缺陷。 在每次迭代中，不是选择当前未访问且距离源节点（初始）最小的节点，而是选择未访问且距离当前节点最近的节点（在每次迭代中更新）。 因此，第0个索引节点正在被访问，但其距离没有得到更新，因此通过该节点的最短路径也没有得到更新

让我们用失败的测试用例对代码进行一次试运行：

初始变量：

graph:[[0.0, 3.0, 1.0, inf, inf, inf, inf],
      [3.0, 0.0, 8.0, 10.0, 5.0, inf, inf],
      [1.0, 8.0, 0.0, inf, inf, inf, inf],
      [inf, 10.0, inf, 0.0, 6.0, inf, 9.0],
      [inf, 5.0, inf, 6.0, 0.0, 1.0, 2.0],
      [inf, inf, inf, inf, 1.0, 0.0, 4.0],
      [inf,inf,inf, 9.0, 2.0, 4.0, 0.0]]
visited: [False, False, False, True, False, False, False]
sp_list: [inf, 10, inf, 0, 6, inf, 9]
current_node: 3 (zero indexing)

第1次迭代：

current_node: 4
sp_list: [inf, 10, inf, 0, 6, 7, 8]
visited: [False, False, False, True, True, False, False]

第二次迭代：

current_node: 5 // Node with shortest distance from node 4 instead of node 3.
sp_list: [inf, 10, inf, 0, 6, 7, 8]
visited: [False, False, False, True, True, True, False]

第三次迭代：

current_node: 6 // node closest to node 5 which is unvisited
sp_list: [inf, 10, inf, 0, 6, 7, 8]
visited: [False, False, False, True, True, True, True]

第4次迭代：

Here is where the problem occurs. If you observe, all the neighbors of node 6 are visited (node 3, node 4 and node 5). So, in this case, the function min_dist_node will return the default value of node, which is 0. But sp_list[0] = inf!, so, the sp_list entries for nodes connected to 0th node will not be updated.

因此：

current_node: 0
sp_list: [inf, 10, inf, 0, 6, 7, 8]
visited: [True, False,False, True, True, True, True]

第5次迭代：

current_node: 2 // node unvisited and closest to 0th node
sp_list: [inf, 10, inf, 0, 6, 7, 8] // same issue as in iteration 4
visited: [True, False,True, True, True, True, True]

第6次迭代：

current_node: 1
sp_list: [13, 10, 18, 0, 6,7,8] // The edge 1 -> 2 will be considered
visited: [True, True ,True, True, True, True, True]

因此，当所有节点都被访问时，循环将结束

因此，解决方案在于选择距离初始节点最近的下一个节点，而不是当前节点。这可以通过在优先级队列中存储节点距离来实现

对于算法的实现，您可以参考this