たのしいPython ダイクストラ法ですべての最短経路を求める

ダイクストラ法ですべての最短経路を求める

Pythonの話というより、グラフ理論アルゴリズムの話になりつつあって、ちょっとマニア度が高くなってきましたが、NetworkXのライブラリに少し手を入れて、すべての最短経路を求められるようなメソッドを作って見ました。
重みつき無向グラフの最短経路（shortest path）を求めるアルゴリズムとして、ダイクストラ法（Dijkstra's algorithm）は有名ですが、これを実装したNetworkXのpathsモジュールのメソッドsingle_source_dijkstra(G,source,target=None): は、sourceから、あるtargetまでの最短経路のうち1つしか返してくれません。同じ最短経路長で、いくつかの経路がある場合、それが全部知りたいと思うのは、自然な発想かと。
また、ダイクストラ法は、そのアルゴリズムの本質的な部分で、すべての可能な最短経路を計算しているので、改変はいたって簡単。ソースを貼り付けておきます。

def single_source_dijkstra_all_paths(G,source,target=None):

　if source==target: return (0, [source])
　dist = {} # dictionary of final distances
　paths = {source:[[source]]} # dictionary of paths
　seen = {source:0}
　fringe=[] # use heapq with (distance,label) tuples
　heapq.heappush(fringe,(0,source))
　if not G.is_directed(): G.successors=G.neighbors
　# if unweighted graph, set the weights to 1 on edges by
　# introducing a get_edge method
　# NB: for the weighted graphs (XGraph,XDiGraph), the data
　# on the edge (returned by get_edge) must be numerical
　if not hasattr(G,"get_edge"): G.get_edge=lambda x,y:1

　while fringe:
　　(d,v)=heapq.heappop(fringe)
　　if v in dist: continue # already searched this node.
　　dist[v] = seen[v]
　　if v == target: break
　　　
　　for w in G.successors(v):
　　　vw_dist = dist[v] + G.get_edge(v,w)
　　　if w in dist:
　　　　if vw_dist < dist[w]:
　　　　　raise ValueError,\
　　　　　　 "Contradictory paths found: negative weights?"
　　　elif w not in seen or vw_dist < seen[w]:
　　　　seen[w] = vw_dist
　　　　heapq.heappush(fringe,(vw_dist,w))
　　　　for _each_path in paths[v]:
　　　　　paths.setdefault(w,[]).append( _each_path + [w] )
　　　elif vw_dist == seen[w]:
　　　　for _each_path in paths[v]:
　　　　　paths[w].append( _each_path + [w] )
　return (dist,paths)

pathsの値に、経路のリストを保持するようにして、ループの際に、これまで見つかっている経路長と同じでも、その経路を保持するようにしただけです。

小規模なグラフで動くことは確認したけど、大規模になったときどうかは、確認する必要があるかも。

スポンサーサイト