# T：最短路徑樹
# 尋找圖形 g 中由起點 s 出發的最短路徑
dijkstra(g, s):
    for v ←0 to g.N-1:
        dist[v] ← INF
        parent[v] ← NIL # 無父節點的狀態

    d[s] ← 0

    while True:
        u ← NIL
        minv ← INF
        # find minimum
        for v ← 0 to g.N-1:
            if v 已在 T 內 : continue
            if dist[v] < minv:
                u ← v
                minv ← dist[v]
 
        if u = NIL: break
        將 u 新增至 T 內
  
        for v ← 0 to g.N-1:
            if weight[u][v] = INF: continue:
            if v 已在 T 內: continue
            if dist[v] > dist[u] + weight[u][v]:
                dist[v] ← dist[u] + weight[u][v]
                parent[v] ← u