python2.7からPriorityQueueが標準モジュールに入ってた

python2.7からQueueモジュールにスタック(LIFOQueue)と優先順位キュー(PriorityQueue)が入ってたので使ってみた。

ダイクストラ法。グラフはwikipediaのダイクストラ法に載ってるやつから作った。

#! /usr/bin/python2.7

import Queue as queue

nnodes = 6
dist = [10**30] * nnodes
prev = [-1] * nnodes
start = 0
edge = [ # weight, src, dst
 ( 7, 0, 1),
 ( 9, 0, 2),
 (14, 0, 5),
 (10, 1, 2),
 (15, 1, 3),
 (11, 2, 3),
 ( 2, 2, 5),
 ( 6, 3, 4),
 ( 9, 4, 5),
]
edge = edge + [(e[0], e[2], e[1]) for e in edge]
q = queue.PriorityQueue()

for e in edge:
    if e[1] == start:
          dist[e[2]] = e[0]
          q.put(e)
prev[start] = start
dist[start] = 0


while not q.empty():
    weight, src, dst = q.get()
    if prev[dst] != -1:
        continue
    for e in edge:
        if e[1] == dst and prev[e[2]] == -1:
            q.put(e)
    prev[dst] = src
    for e in edge:
        if e[1] == dst and dist[dst] + e[0] < dist[e[2]]:
           dist[e[2]] = dist[dst] + e[0]

print(prev)
print(dist)