Pythonで迷路を解く - アルゴリズムクイックリファレンス６章の補足 - ref: http://qiita.com/sasanquaneuf/items/77bf6518b4bf97bcd15b

BreadthFirst.py

# 幅優先探索
import copy

# 近傍、使用済みフラグ（世代）の定義
verts = range(1,vs + 1)
verts.append('s')
verts.append('t')
neighbor = {}
used = {}
used['t'] = 0
for v in verts:
    neighbor[v] = {}
    used[v] = 0
used['s'] = 1
for (s, t, d) in edges:    
    neighbor[s][t] = d
    neighbor[t][s] = d

queue = list()
queue.append('s')
while len(queue) > 0:
    t = queue.pop(0)
    for n in neighbor[t]:
        if used[n] == 0:
            used[n] = used[t] + 1
            queue.append(n)

used

CreateGraph.py

# 迷路をグラフにする：本質的に深さ優先探索
import itertools as it

def isWall(s):
    return 1 if s == '$' else 0

def getWalls(arr, i, j):
    return isWall(arr[i+1][j]) + isWall(arr[i-1][j]) + isWall(arr[i][j+1]) + isWall(arr[i][j-1])

def getEdge(arr, i, j, edges, v, c):
    for (a,b) in zip([1,-1,0,0], [0,0,1,-1]):
        if isWall(arr[i+a][j+b]) == 0:
            arr[i+a][j+b] = '$'
            if arr[i+2*a][j+2*b] == 0:
                vn = v
                cn = c + 1
            else:
                vn = arr[i+2*a][j+2*b]
                edges.append((v, vn, c))
                cn = 1
            getEdge(arr, i+2*a, j+2*b, edges, vn, cn)

vs = 0
edges = list()
arr = list()
for line in open('maze_input.txt', 'r'):
    arr.append(list(line))
height = len(arr)
width = len(arr[height - 1])
cellidi = range(1,width,2)
cellidj = range(1,height,2)
for i,j in it.product(cellidi, cellidj):
    if getWalls(arr, i, j) == 2:
        arr[i][j] = 0
    elif arr[i][j] == ' ':
        vs += 1
        arr[i][j] = vs

# 今回のデータ用の設定
getEdge(arr, 3, 7, edges, 1, 1)

Dijkstra.py

# 最短コストの経路のダイクストラ法による算出
costs = {}
# costs[v] = (cost, prev, used)の組
for v in verts:
    costs[v] = (float("inf"),0,0)
costs['s'] = (0,-1,0)

queue = list()
queue.append('s')
while len(queue) > 0:
    t = queue.pop(0)
    costs[t] = (costs[t][0], costs[t][1], 1)
    for n in neighbor[t]:
        if costs[n][2] == 0 and costs[n][0] > neighbor[t][n] + costs[t][0]:
            costs[n] = (neighbor[t][n] + costs[t][0], t, 0)
    # queueへの入れ方を工夫すればもっと早くなるが、ここではqueueには最低の値を一つ入れるだけにする
    mincost = float("inf")
    minv = 's'
    for v in verts:
        if mincost > costs[v][0] and costs[v][2] == 0:
            mincost = costs[v][0] 
            minv = v
    if minv != 's':
        queue.append(minv)

maze_input.txt

$$$$$$$$$$$$$$$$$
$   $   $       $
$ $ $ $ $ $$$$$ $
$ $ $ $ $ $   $ $
$ $ $ $$$ $ $ $ $
$ $ $   $ $ $   $
$ $ $ $ $ $ $$$$$
$ $ $ $ $t$   $ $
$ $$$ $ $$$ $ $ $
$     $     $ $ $
$ $$$ $ $$$ $ $ $
$ $   $ $   $   $
$$$ $$$$$ $$$ $ $
$   $         $ $
$ $$$ $$$$$$$$$ $
$    s          $
$$$$$$$$$$$$$$$$$

Visualize.py

# 可視化
import networkx as nx
import matplotlib.pyplot as plt
import math

G = nx.Graph()
srcs, dests = zip(* [(fr, to) for (fr, to, d) in edges])
G.add_nodes_from(srcs + dests)

for (s,r,d) in edges:
    G.add_edge(s, r, weight=20/math.sqrt(d))

pos = nx.spring_layout(G)

edge_labels=dict([((u,v,),d)
             for u,v,d in edges])

plt.figure(1)
nx.draw_networkx(G, pos, with_labels=True)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)

plt.axis('equal')
plt.show()

結果

{1: (13, 2, 1),
 2: (9, 7, 1),
 3: (17, 6, 1),
 4: (7, 9, 1),
 5: (9, 13, 1),
 6: (9, 7, 1),
 7: (7, 's', 1),
 8: (8, 9, 1),
 9: (6, 14, 1),
 10: (10, 6, 1),
 11: (9, 8, 1),
 12: (6, 14, 1),
 13: (7, 's', 1),
 14: (3, 's', 1),
 's': (0, -1, 1),
 't': (20, 4, 1)}