# T: 最短経路木
# グラフgについて始点sからの最短経路を求める
# g.N: グラフgのノードの数
dijkstra(g, s):
    for v ← 0 to g.N - 1:
        dist[v] ← INF
        parent[v] ← NIL # 親がない状態

    Tを空にする
    dist[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
        Tにuを含める
  
        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