图最短路径算法(Dijkstra) -- Python

狄克斯特拉（Dijkstra）算法也是求解最短路径问题的算法，使用它可以求得从起点到终点的路径中权重总和最小的那条路径路径。
使用优先队列来实现，优先队列是依据二叉堆实现

无向图

import heapq
import math
graph = {
    "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}
}

def init_distance(graph,s):
    distance = {s:0}
    for vertex in graph.keys():
        if vertex != s:
            distance[vertex] = 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[0]
        vertex = pair[1]
        seen.add(vertex)

        nodes = graph[vertex].keys() # 与vertex 相邻的结点
        for w in nodes:
            if w not in seen: # 如果结点没有弹出
                if dist + graph[vertex][w] < distance[w]:
                    heapq.heappush(pqueue,(dist+graph[vertex][w],w))
                    parent[w] = vertex
                    distance[w] = dist + graph[vertex][w]
    return parent,distance

parent,distance = dijkstra(graph,"A")
print(f"parent:{parent}")
print(f"distance:{distance}")

"""
results:
parent:{'A': None, 'B': 'C', 'C': 'A', 'D': 'B', 'E': 'D', 'F': 'D'}
distance:{'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7, 'F': 10}
"""

有向图

# 有向图
import math
import heapq

graph = {
    "V0":{"V2":10,"V4":30,"V5":100},
    "V1":{"V2":5},
    "V2":{"V3":50},
    "V3":{"V5":10},
    "V4":{"V3":20,"V5":60},
    "V5":{"V5":0}
}

def init_distance(graph,s):
    distance = {s:0}
    for key in graph.keys():
        if key != s:
            distance[key] = math.inf

    return distance

def dijkstra(graph,s):
    pqueue = []
    heapq.heappush(pqueue,(0,s))
    seen = set()

    path = {s:None}
    distance = init_distance(graph,s)
    while len(pqueue) > 0:
        pair = heapq.heappop(pqueue)
        dist = pair[0]
        vertex = pair[1]
        seen.add(vertex)

        nodes = graph[vertex].keys()
        for m in nodes:
            if m not in seen:
                if dist + graph[vertex][m] < distance[m]:
                    heapq.heappush(pqueue,(dist + graph[vertex][m],m))
                    distance[m] = dist + graph[vertex][m]
                    path[m] = vertex

    return path,distance

path,distance = dijkstra(graph,"V0")
print(path)
print(distance)

"""
results:
	{'V0': None, 'V2': 'V0', 'V4': 'V0', 'V5': 'V3', 'V3': 'V4'}
	{'V0': 0, 'V1': inf, 'V2': 10, 'V3': 50, 'V4': 30, 'V5': 60}
"""