ダイクストラの最短経路アルゴリズム

courseraで課題になってたのでいろいろ参考にしながらpythonで実装した。

参考ページ
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode
http://taichino.com/programming/1333

./dijkstra.py graph_file start end のようにオプションを渡す。
graphデータのファイルは、各行に、vertexと、隣接したvertex,lengthを記述したもの。

1 2,3 3,3
2 3,1 4,2
3 4,50
4

#!/usr/bin/env python

import sys
from altgraph import Graph

def read_graph(f):
    g = Graph.Graph()
    for l in file(f):
        l = l.rstrip().split()
        # read vertex
        v = int(l[0])
        l.pop(0)

        # read neighbor & length
        for i in l:
            i = i.split(',')
            g.add_edge(v, int(i[0]), int(i[1]))

    return g

def dijkstra(graph, start):
    dist = {}
    for v in graph.nodes:
        dist[v] = sys.maxint

    prev = {}
    for v in graph.nodes:
        prev[v] = None

    dist[start] = 0
    Q = graph.nodes.copy()

    while len(Q):
        # find vertex with smallest distance.
        min_dist = sys.maxint
        u = Q.keys()[0] # first vertex
        for v in Q:
            if dist[v] < min_dist:
                u = v
                min_dist = dist[v]

        del(Q[u])
        if dist[u] == sys.maxint:
            break

        # find neighbors
        neighbors = {}
        for e in graph.edges.values():
            if e[0] == u:
                neighbors[e[1]] = e[2]

        for v in neighbors:
            alt = dist[u] + neighbors[v]
            if alt < dist[v]:
                dist[v], prev[v] = alt, u
    return dist, prev

if __name__=='__main__':
    if len(sys.argv) > 2:
        graph_file = sys.argv[1]
        start = int(sys.argv[2])
        end = int(sys.argv[3])

        g = read_graph(graph_file)
        dis = dijkstra(g, start)
        print dis[0][end]

1->3への最短経路

$ ./dijkstra.py graph.txt 1 3
3