4

エッジの重み/距離が負の場合に最短経路の距離を見つけるために、Bellman-Ford を正常に実装しました。すべての最短パスを返すようにすることはできませんでした (最短のタイがある場合)。Dijkstra を使用して、(指定されたノードのペア間の) すべての最短パスを取得することができました。これは Bellman-Ford で可能ですか? （私が時間を無駄にしているかどうか知りたいだけです）

4

1 に答える 1

8

Bellman-Ford アルゴリズムの 2 番目のステップを少し変更すると、非常によく似た結果が得られます。

for i from 1 to size(vertices)-1:
   for each edge uv in edges: // uv is the edge from u to v
       u := uv.source
       v := uv.destination
       if u.distance + uv.weight < v.distance:
           v.distance := u.distance + uv.weight
           v.predecessor[] := u
       else if u.distance + uv.weight == v.distance:
           if u not in v.predecessor:
               v.predecessor += u

はv.predecessor頂点のリストです。の新しい距離がvまだ含まれていないパスに等しい場合、新しい前任者を含めます。

すべての最短パスを出力するには、次のようなものを使用できます

procedure printPaths(vertex current, vertex start, list used, string path):
    if current == start:
        print start.id + " -> " + path
    else:
        for each edge ve in current.predecessors:
            if ve.start not in used:
                printPaths(ve.start,start, used + ve.start, ve.start.id + " -> " + path)

printPaths(stop,start,stop,stop.id)すべてのパスを出力するために使用します。

注:if u not in v.predecessor then v.predecessor += uアルゴリズムの終了後に重複する要素を削除すると、変更されたアルゴリズムから除外することができます。

于 2012-07-07T00:03:57.703 に答える