# 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
        将 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