<p>更新!我找到了一种不使用优先级队列的解决方法。如果我们将dist>;=图[初始] [i]我们首先考虑所有距离(从初始节点)不等INF,然后考虑所有的INF。p>
<p>我认为这是正确的方法,如果有人看到一些错误,请告诉我</p>
<p>这就是所有算法现在的样子:</p>
<pre><code>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)
</code></pre>