16

ノード/頂点のすべてのペア間の最短パスの距離と、これらの各ペア間の単一の最短パスを返すために、Floyd-Warshall を実装しました。

ノードのすべてのペアに対して、最短で結ばれている複数のパスがある場合でも、すべての最短パスを返すようにする方法はありますか? （私が時間を無駄にしているかどうか知りたいだけです）

4

3 に答える 3

12

異なる最短パスがいくつ存在するかだけが必要な場合は、count配列に加えて配列を保持できますshortestPath。これは、 wikiからの疑似コードの簡単な変更です。

procedure FloydWarshall ()
    for k := 1 to n
        for i := 1 to n
            for j := 1 to n
                if path[i][j] == path[i][k]+path[k][j] and k != j and k != i
                    count[i][j] += 1;
                else if path[i][j] > path[i][k] + path[k][j]
                    path[i][j] = path[i][k] + path[k][j]
                    count[i][j] = 1

すべてのパスを見つける方法が必要な場合は、vector/arraylist各ペアの like 構造を格納して、展開と折りたたみを行うことができます。これは、同じwikiからの疑似コードの変更です。

procedure FloydWarshallWithPathReconstruction ()
    for k := 1 to n
        for i := 1 to n
            for j := 1 to n
                if path[i][k] + path[k][j] < path[i][j]
                    path[i][j] := path[i][k]+path[k][j];
                    next[i][j].clear()
                    next[i][j].push_back(k) // assuming its a c++ vector
                else if path[i][k] + path[k][j] == path[i][j] and path[i][j] != MAX_VALUE and k != j and k != i
                    next[i][j].push_back(k)

注: または の場合k==j、またはのいずれかk==iをチェックしていることを意味し、両方が等しい必要があり、 にプッシュされません。path[i][i]+path[i][j]path[i][j]+path[j][j]path[i][j]next[i][j]

を処理するには、パスの再構築を変更する必要がありvectorます。この場合のカウントは、それぞれvectorのサイズになります。これは、同じwikiからの疑似コード (python) の変更です。

procedure GetPath(i, j):
    allPaths = empty 2d array
    if next[i][j] is not empty:
        for every k in next[i][j]:
            if k == -1: // add the path = [i, j]
                allPaths.add( array[ i, j] ) 
            else: // add the path = [i .. k .. j]
                paths_I_K = GetPath(i,k) // get all paths from i to k
                paths_K_J = GetPath(k,j) // get all paths from k to j
                for every path between i and k, i_k in paths_I_K:
                    for every path between k and j, k_j in paths_K_J:
                        i_k = i_k.popk() // remove the last element since that repeats in k_j
                        allPaths.add( array( i_k + j_k) )

    return allPaths

注:path[i][j]は隣接リストです。を初期化するときに、配列にa を追加してpath[i][j]初期化することもできます。たとえば、の初期化は次のようになりますnext[i][j]-1next[i][j]

for every edge (i,j) in graph:
   next[i][j].push_back(-1)

これにより、エッジ自体が最短経路であることが処理されます。パスの再構築でこの特殊なケースを処理する必要があります。これは、私がGetPath.

編集:「MAX_VALUE」は、距離の配列の初期化された値です。

于 2012-07-07T01:35:29.020 に答える
9

現在承認されている回答の「カウント」機能が失敗する場合があります。より完全な解決策は次のとおりです。

procedure FloydWarshallWithCount ()
for k := 1 to n
    for i := 1 to n
        for j := 1 to n
            if path[i][j] == path[i][k]+path[k][j]
                count[i][j] += count[i][k] * count[k][j]
            else if path[i][j] > path[i][k] + path[k][j]
                path[i][j] = path[i][k] + path[k][j]
                count[i][j] = count[i][k] * count[k][j]

この理由は、任意の 3 つの頂点 i、j、および k について、i から k を通って j に至る複数の最短経路が存在する可能性があるためです。たとえば、グラフでは次のようになります。

       3             1
(i) -------> (k) ---------> (j)
 |            ^
 |            |
 | 1          | 1
 |     1      |
(a) -------> (b)

i から k を介して j に至る 2 つのパスがあります。count[i][k] * count[k][j]i から k までのパスの数と k から j までのパスの数を求め、それらを乗算して、パスの数 i -> k -> j を求めます。

于 2014-12-08T05:39:54.160 に答える