ダイクストラ法：ソフトウェアデザイン 10月号のけんちょんさんの記事内容を元にPythonでAOJの問題を問いてみた

#解いた問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A

#ソース

• AOJの問題は始点の指定があることに注意
• 蟻本ではフラグを使って更新の有無を確認していたが、けんちょんさんのやり方は、更新されなければ確定（優先度付きキューに入れない）という手法。
• 優先度付きキューをpopして取得した頂点（スタートからの距離が最小の頂点）から探索をする。

import heapq
INF = 10**10

class Edge:
    to = -1
    w = -1
    def __init__(self, to, w):
        self.to = to
        self.w = w

def Dijkstra(Graph, s):
    dist = [INF] * len(Graph)
    dist[s] = 0

    prev = [-1] * len(Graph)

    #スタート頂点をキューに入れる
    #[該当頂点までの最短距離（現時点）,該当頂点のインデックス]
    que = [[0,s]]

    #優先度付きキューに変換
    heapq.heapify(que)

    while len(que) > 0:
        # 優先度付きキューの先頭の要素を取り出す
        # vは頂点番号, dは該当頂点までの現在の最短距離
        p = heapq.heappop(que)
        v = p[1]
        d = p[0]

        #ソフトウェアデザインだと以下処理があるが不要？
        #必要性がよくわからん
        #if d > dist[v]:
        #   continue

        #該当頂点vから行くことのできる頂点毎に距離を計算
        for e in Graph[v]:
            #最短距離を更新できない場合は何もしない
            if dist[v] + e.w >= dist[e.to] :
                continue

            #以下は、最短距離を更新できた場合

            #優先度付きキューに行先頂点の情報をプッシュ
            heapq.heappush(que,[dist[v] + e.w, e.to])

            #行先の最短距離を更新
            dist[e.to] = dist[v] + e.w

            #行先の前のノードを記憶
            #AOJの問題では使わない
            prev[e.to] = v

    for d in dist:
        if d == INF:
            print("INF")
        else:
            print(d)

    return

def main():
    n, m, s = map(int, input().split())
    Graph =  [[] for j in range(n)]
    for i in range(m):
        a, b, w = map(int, input().split())
        Graph[a].append(Edge(b, w))
        #AOJの問題は有効グラフ（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A）
        #Graph[b].append(Edge(a, w))

    Dijkstra(Graph, s)

main()