[ダイクストラ法]pythonで実装して最短経路と経路復元問題を解く

import heapq
inf = float('INF')
def dijkstra(s, G):
    """
    s:スタート地点
    G: 隣接グラフ [ [(v0,d0),...,(vj, dj)],..., [(v2,d2)]]
    """
    n = len(G) #頂点数
    dist = [inf]*n #スタート地点からの距離のリスト
    dist[s] = 0 #スタート地点
    seen = [False]*n #探索済みかどうか管理
    hq = [(0,s)] #ヒープの都合上、(距離, 頂点番号)の並び
    heapq.heapify(hq) #ヒープ化
    
    while hq:
        v = heapq.heappop(hq)[1] #次のノード
        seen[v] = True

        for to,cost in G[v]:
            if seen[to]==False and dist[v]+cost < dist[to]:
                dist[to] = dist[v]+cost
                heapq.heappush(hq, (dist[to], to))
    return dist

G = [[(1, 1), (4, 2)], [(2, 2), (5, 3)], [(1, 3)], []]
dists = dijkstra(0, G) #スタート地点 0
for i in range(len(dists)):
    print(f"頂点{i} への距離は {dists[i]}")

#頂点0 への距離は 0
#頂点1 への距離は 1
#頂点2 への距離は 3
#頂点3 への距離は 4

import heapq
inf = float('INF')
def dijkstra(s, G):
    """
    s:スタート地点
    G: 隣接グラフ [ [(v0,d0),...,(vj, dj)],..., [(v2,d2)]]
    """
    n = len(G) #頂点数
    dist = [inf]*n #スタート地点からの距離のリスト
    dist[s] = 0 #スタート地点
    seen = [False]*n #探索済みかどうか管理
    prev = [-1]*n    #経路復元用のリスト.直前までいたノード番号を管理
    hq = [(0,s)] #ヒープの都合上、(距離, 頂点番号)の並び
    heapq.heapify(hq) #ヒープ化
    
    while hq:
        v = heapq.heappop(hq)[1] #次のノード
        seen[v] = True
        for to in G[v]:
            
            #未探索　かつ　行先のコストが小さくなる場合　は更新
            if seen[to]==False and dist[v]+1 < dist[to]:
                dist[to] = dist[v]+1
                prev[to] = v           #ノードtoに到達する直前にいたノードがv
                heapq.heappush(hq, (dist[to], to))
    
    return dist,prev

#prevから頂点tへの経路を計算する
def get_path(t, prev):
    path = []
    while t !=-1:
        path.append(t)
        t = prev[t]
    #ゴールからスタート地点へ遡る形のため、
    #順番を反転させて返す
    return path[::-1]

G = [[(1, 1), (4, 2)], [(2, 2), (5, 3)], [(1, 3)], []]
dist, prev = dijkstra(0, G) #スタート地点 0
path = get_path(3, prev)    #dijkstraで得られたprevを用いて3へのノードを計算
print(path)
#[0, 1, 2, 3]        #頂点0->頂点1->頂点2->頂点3の順番に到達した。