スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
【--/--/-- --:--】 | スポンサー広告 | page top↑
ダイクストラ法ですべての最短経路を求める
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の値に、経路のリストを保持するようにして、ループの際に、これまで見つかっている経路長と同じでも、その経路を保持するようにしただけです。

小規模なグラフで動くことは確認したけど、大規模になったときどうかは、確認する必要があるかも。
スポンサーサイト
【2006/10/17 21:03】 | Python | トラックバック(0) | コメント(2) | page top↑
<<リスト内包表記 | ホーム | psycoで高速化>>
コメント
初めまして、情報処理の勉強をしていてこちらにたどり着きました。

勉強したことを実際にプログラムにするのは、なかなか面倒でやれてませんが、とても面白そうです!

また、よろしくお願いいたします。
【2013/08/01 23:07】 URL | 師子乃 #55zC9p1w[ 編集] | page top↑
ありがとうございます。
試してみようと思いつつ、後回しになってしまうことよくありますよね・・・。やってみると、また違った発見があったりすると思うので、こちらこそよろしくお願いしますー。
【2013/08/02 09:16】 URL | 辻真吾(つじしんご) #-[ 編集] | page top↑
コメントの投稿














管理者にだけ表示を許可する

トラックバック
トラックバックURL
→http://tanopy.blog79.fc2.com/tb.php/4-c44daaf4
この記事にトラックバックする(FC2ブログユーザー)
| ホーム |
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。