単一始点最短路問題

V, E = 7, 10 # 頂点の数、辺の数
inf = float('INF')
# cost[u][v] は辺e = (u, v) のコスト（存在しない場合は inf）
cost = [[  0,   2,   5, inf, inf, inf, inf],  #頂点A
        [  2,   0,   4,   6,  10, inf, inf],  #頂点B
        [  5,   4,   0,   2, inf, inf, inf],  #頂点C
        [inf,   6,   2,   0, inf,   1, inf],  #頂点D
        [inf,  10, inf, inf,   0,   3,   5],  #頂点E
        [inf, inf, inf,   1,   3,   0,   9],  #頂点F
        [inf, inf, inf, inf,   5,   9,   0]]  #頂点G
d = {} #最短距離を格納する辞書
used = {} #すでに使われたか？のフラグ
prev = {} #最短路の直前の頂点
# 始点 sから各頂点への最短距離を求める
def dijkstra(s):
    # inf で初期化    
    for v in range(V):
        d[v] = inf
    # False で初期化   
    for v in range(V):
        used[v] = False
    # -1 で初期化
    for v in range(V):
        prev[v] = -1
    #始点から始点のへの距離は（当たり前に）0
    d[s] = 0
    while True:
        v = -1
        for u in range(V):
            if used[u] == False and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        for u in range(V):
            if d[u] > d[v] + cost[v][u]:
                d[u] = d[v] + cost[v][u]
                prev[u] = v
# 頂点sから 頂点tへの最短路をリストへ記入
def get_path(s, t):
    path = []
    # tがsになるまで prev[t] を辿っていく
    while t != s:
        path.append(t)
        t = prev[t]
    path.append(s)
    return path[::-1] #このままだと t -> sの順になっているので逆順にする

#実行部
dijkstra(0)
path = get_path(0, 6)
print(path) # --> [0, 2, 3, 5, 4, 6]