python 上 Dijkstra 算法实现的断言错误
Assertion error on Dijkstra algorithm implementation on python
我有这个 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)
逻辑好像有问题。
在每次迭代中，不是拾取当前未访问的节点并且与源节点（初始） 的距离最小 ，而是选择未访问的节点并且 最接近 current_node（在每次迭代中更新）。
因此，第 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)
第一次迭代：
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
更新！我找到了一种不使用优先级队列的解决方法。在 min_dist_node 函数中，如果我们放置 dist >= graph[initial][i] 我们将首先考虑所有距离（从初始节点开始）不等于 inf，然后是所有 inf。
我认为这是正确的方法，如果有人发现错误请告诉我！
这就是所有算法现在的样子：
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)
我有这个 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)
逻辑好像有问题。 在每次迭代中，不是拾取当前未访问的节点并且与源节点（初始） 的距离最小 ，而是选择未访问的节点并且 最接近 current_node（在每次迭代中更新）。 因此，第 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)
第一次迭代：
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
更新！我找到了一种不使用优先级队列的解决方法。在 min_dist_node 函数中，如果我们放置 dist >= graph[initial][i] 我们将首先考虑所有距离（从初始节点开始）不等于 inf，然后是所有 inf。
我认为这是正确的方法，如果有人发现错误请告诉我！
这就是所有算法现在的样子：
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)