Python实现Dijkstra算法
<pre><code># Dijkstra.狄杰斯特拉import heapq
import math
def init_distance(graph, s):
distance = {s: 0}
for vertex in graph:
if vertex != s:
distance = math.inf
return distance
def dijkstra(graph, s):
pqueue = []
heapq.heappush(pqueue, (0, s))
seen = set()
parent = {s: None}
distance = init_distance(graph, s)
while len(pqueue) > 0:
pair = heapq.heappop(pqueue)
dist = pair
vertex = pair
seen.add(s)
nodes = graph.keys()
for w in nodes:
if w not in seen:
if dist + graph < distance:
heapq.heappush(pqueue, (dist + graph, w))
parent = vertex
distance = dist + graph
return parent, distance
if __name__ == '__main__':
graph_dict = {
"A": {"B": 5, "C": 1},
"B": {"A": 5, "C": 2, "D": 1},
"C": {"A": 1, "B": 2, "D": 4, "E": 8},
"D": {"B": 1, "C": 4, "E": 3, "F": 6},
"E": {"C": 8, "D": 3},
"F": {"D": 6},
}
parent_dict, distance_dict = dijkstra(graph_dict, "A")
print(parent_dict)
print(distance_dict)
</code></pre><br><br>
来源：https://www.cnblogs.com/c-x-a/p/11004242.html
頁:
[1]