ダイクストラ法

プログラミングコンテストチャレンジブックにダイクストラ法（Dijkstra's algorithm）の説明が載っていた。Wikipediaに書いてあった説明は意味が分からなかったが、これはわかりやすい。
これは、Project Euler Problem 83を解くときに思いついた方法そのものだ。すなわち、ダイクストラ法は適切な例題さえあれば誰でも思いつく可能性があるアルゴリズムだ。
Priority Queueを使ってProblem 83のコードを書き直してみた。

from Queue import PriorityQueue

def gen_neighbor(x, y):
    if x > 0:
        yield x - 1, y
    if x < N - 1:
        yield x + 1, y
    if y > 0:
        yield x, y - 1
    if y < N - 1:
        yield x, y + 1

file = open("matrix.txt")
a = [ map(int, s.split(',')) for s in file.readlines() ]
N = len(a)
M = len(a[0])
b = [ [ 10 ** 9 ] * M for n in range(N) ]
q = PriorityQueue()
q.put((a[0][0], (0, 0)))
while True:
    s, (x, y) = q.get()
    if (x, y) == (M - 1, N - 1):
        break
    if b[x][y] <= s:
        continue
    
    b[x][y] = s
    for x1, y1 in gen_neighbor(x, y):
        s1 = s + a[x1][y1]
        if b[x1][y1] < s1:
            continue
        q.put((s1, (x1, y1)))
print s

実にシンプルに書ける。このPriorityQueueは小さい値から順に取り出されるが、タプルは頭の要素から順に比較されるので、上のように書くことができる。

print (1, 3) < (2, 1)   # True

さて、これを動かしてみると、オリジナルより3倍くらい遅くなった。オリジナルはPriorityQueueではなくリスト（STLでいうvectorのようなもの、たぶん）を使っている。やはり、もっと規模が大きくないと効果が現れないか。