最短路径算法之Dijkstra算法

# Dijkstra算法——通过边实现松弛
# 指定一个点到其他各顶点的路径——单源最短路径

# 每次找到离源点最近的一个顶点，然后以该顶点为重心进行扩展
# 最终的到源点到其余所有点的最短路径
# 一种贪婪算法

def Dijkstra(G, v0, INF = float('inf')):
    """ 使用 Dijkstra 算法计算指定点 v0 到图 G 中任意点的最短路径的距离 INF 为设定的无限远距离值 此方法不能解决负权值边的图 """
    book = set()
    minv = v0

    # 源顶点到其余各顶点的初始路程
    dis = dict((k, INF) for k in G.keys())
    dis[v0] = 0

    while len(book) < len(G):
        book.add(minv)  # 确定当期顶点的距离
        for w in G[minv]:  # 以当前点的中心向外扩散
            if dis[minv] + G[minv][w] < dis[w]:  # 如果从当前点扩展到某一点的距离小与已知最短距离
                dis[w] = dis[minv] + G[minv][w]  # 对已知距离进行更新

        new = INF  # 从剩下的未确定点中选择最小距离点作为新的扩散点
        for v in dis.keys():
            if v in book: continue
            if dis[v] < new:
                new = dis[v]
                minv = v
    return dis

if __name__ == '__main__':
    # 初始化图参数
    G = {
   1: {
   1: 0, 2: 2, 4: 1, 6: 3},
         2: {
   2: 0, 3: 6, 5: 5},
         3: {
   3: 0, 8: 6},
         4: {
   2: 10, 4: 0, 7: 2},
         5: {
   5: 0, 3: 9, 8: 4},
         6: {
   6: 0, 4: 5, 7: 4},
         7: {
   2: 7, 5: 3, 8: 8, 7: 0},
         8: {
   8: 0}}

    start = 1
    dis = Dijkstra(G, v0 = start)
    print(dis)
最短路径算法之Dijkstra算法

参考：
