6

sとtの頂点を持つグラフがあり、その間の最短経路を見つける必要があります。グラフには、私が利用したい多くの特別なプロパティがあります。

  • グラフはDAG（有向非巡回グラフ）です。
  • 従来のO（| V + E |）よりも速く、O（| V |）時間でトポロジカルソートを作成できます。
  • トポロジカルソート内で、sはリストの最初の項目であり、tは最後の項目です。

トポロジカルソートの頂点を取得すると、ダイクストラの均一コストの現在の標準よりも速く最短経路を見つけることができると言われましたが、そのアルゴリズムを見つけることができないようです。

擬似コードをいただければ幸いです。

編集：sからtまでのすべてのパスは同じ数のエッジを持っています。エッジには重みがあります。最低コストのパスを探しています。

4

1 に答える 1

22

直感に反して、これは宿題ではないと仮定します。トポロジー順序付けによって得られる情報を活用する必要があります。ノード n をトポロジー順序で調べるときはいつでも、n へのすべての可能なパスを既に通過したことが保証されます。これを使用すると、トポロジカル順序 (疑似コード) の 1 回の線形スキャンで最短パスを生成できることが明らかです。

Graph g
Source s
top_sorted_list = top_sort(g)

cost = {} // A mapping between a node, the cost of its shortest path, and 
          //its parent in the shortest path

for each vertex v in top_sorted_list:
  cost[vertex].cost = inf
  cost[vertex].parent = None

cost[s] = 0

for each vertex v in top_sorted_list:
   for each edge e in adjacensies of v:
      if cost[e.dest].cost > cost[v].cost + e.weight:
        cost[e.dest].cost =  cost[v].cost + e.weight
        e.dest.parent = v

これで、s から目的地までの最短経路を調べることができます。コスト マッピングで宛先を検索し、その親を取得し、親が s であるノードが取得されるまでこのプロセスを繰り返すだけで、最短パスが得られます。

于 2009-09-27T03:05:32.563 に答える