ダイクストラ法

技術全般 Python

前回のアルゴリズムイントロダクション輪講の話題、単一始点最短路問題から。詳しくは アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー へ。その中で丁度前回 書いたプリム法と同じく、ダイクストラ法が最小優先度付きキューを使うので、ちょっといじったらかけるのでは？と思って書いてみました。(相変わらずの乱プログラムご容赦...)。対象のグラフは教科書通り。

実装的には、minheap クラスは前回のプリム法と全く一緒。MinPriorityQueue は前回と使い方が違うので一部実装し直し。(といっても relax の周り)。実行するとこんな感じになるはずです。

s -> y -> t  (8)
s -> y -> t -> x  (9)
s -> y  (5)
s -> y -> z  (7)
  • 教科書のヒープソート (6章) にもあったように、優先度付きキューの実装はそのヒープのキー値と実際のオブジェクトの紐付けが肝、という事を体感。
  • 使うデータ構造が近いと、なんとなく実装から香り立つ雰囲気も近い (?!)
  • 前回のコードをみて、点 (Vertex) のクラス名が Vertice になっている事に気づく。ハズカス。もうそのままにしときます。。
# -*- coding: utf-8 -*-

import sys
from heapq import heappush,heappop

class minheap:    
    
    def __init__(self,elems):
        self.heap = []
        [heappush(self.heap,e) for e in elems]
        
    def extract_min(self):
        return heappop(self.heap)
    
    def decrease_key(self,i,key):
        if key > self.heap[i] :
            raise Exception, "new key is larger than current key"
        self.heap[i] = key
        while i > 0 and self.heap[i/2] > self.heap[i] :
            pindex = i/2
            self.heap[i], self.heap[pindex] = self.heap[pindex], self.heap[i]
            i = pindex
            
    def index(self,key):
        return self.heap.index(key)
    
    def is_empty(self):
        return len(self.heap) == 0
    
class MinPriorityQueue:
    
    def __init__(self,elems):
        keys = map(lambda x : x.d, elems)
        self.minheap = minheap(keys)
        self.key_elem_handles = dict([(k,[]) for k in keys])
        [self._update_key_elem_handles(e) for e in elems]
        
    def is_phi(self):
        return self.minheap.is_empty()
    
    def extract_min(self):
        min_key = self.minheap.extract_min()    
        elem = self.key_elem_handles[min_key].pop(0)
        return elem
    
    def relax(self,u,v):
        if v.d > u.d + u.w(v) :
            self._update(v, u.d + u.w(v))
            v.pi = u 
    
    def _update(self,elem,d):        
        oldkey = elem.d
        i = self.minheap.index(oldkey)
        self.minheap.decrease_key(i, d)
        self.key_elem_handles[oldkey].remove(elem)
        elem.d = d
        self._update_key_elem_handles(elem)
    
    def _update_key_elem_handles(self,elem):
        key = elem.d
        if not self.key_elem_handles.has_key(key) :
            self.key_elem_handles[key] = []
        self.key_elem_handles[key].append(elem)

class Vertex:    
    
    def __init__(self,name):
        self.name = name
        self.adjs = dict()        
        
    def add(self,vertex,weight):
        if not self.adjs.has_key(vertex) :
            self.adjs[vertex] = weight
        return self
    
    def w(self,vertex):
        return self.adjs.get(vertex,sys.maxint)
    
    def adj(self):
        return self.adjs.keys()    

    def __repr__(self):
        return self.name
    
    __str__ = __repr__
    
def initialize_single_source(vertices,s):
    for v in vertices :
        v.d = sys.maxint
        v.pi = None
    s.d = 0
    
def paint_path(vertices,s,v, first=False):
    if v == s :
        print s,
    else :
        if v.pi is None :
            print "no route found from %s to %s" % s,v
        else :
            paint_path(vertices,s,v.pi)
            print "-> %s" % v,
            if first :
                print " (%d)" % v.d
                            
# vertices
s,t,x,y,z = Vertex('s'), Vertex('t'), Vertex('x'), Vertex('y'), Vertex('z')
vertices = [s,t,x,y,z]

s.add(t,10).add(y,5)
t.add(x,1).add(y,2)
x.add(z,4)
y.add(t,3).add(x,9).add(z,2)
z.add(s,7).add(x,6)

# DIJKSTRA
initialize_single_source(vertices, s)
Q = MinPriorityQueue(vertices)
while not Q.is_phi() :
    u = Q.extract_min()
    for v in u.adj() :
        Q.relax(u, v)

# output
for dest in [t,x,y,z] :    
    paint_path(vertices,s,dest,True)