4

nノードの有向加重グラフの最短経路問題を解くときに、各最短経路がmステップ以下になるように、Floyd-Warshall アルゴリズムを変更することは可能ですか? より正確には、ノードiとjの各ペアについて、 m個以下のノードを含むiからjへの最短の有向パスを見つけようとしています。時間計算量はまだO ( n 3 ) のままですか?

4

3 に答える 3

2

一方、パスがm個を超えるノードを含まないように、 n 個のノードを持つグラフの全ペア最短パス (ASPP) 問題を見つけるためのO ( n 3 log m ) アルゴリズムを見つけました。

2 つのn x n行列、たとえばA = [ a ij ] とB = [ b ij ] が与えられると、それらの距離積はn x n行列C = [ c ij ] = A x Bであり、 c ij = min 1≤ kで定義されます。 ≤ n { a ik + b kj }。

これは、ASPP と次のように関連しています。グラフ内の距離の加重行列Eが与えられると、 E nはすべてのペアの最短経路の行列です。どのパスにもm個を超えるノードが含まれていないという制約を追加すると、行列E mが ASPP の解になります。計算能力はO (log m ) 時間で求められるため、これによりO ( n 3 log m ) アルゴリズムが得られます。

ここでは、いくつかの特別なケースで行列の距離積を計算するためのより高速なアルゴリズムを見つけることができますが、全体の時間はフロイド-ウォーシャル アプローチとほぼ同じくらい速いため、簡単なものO ( n 3 ) で十分です。

于 2014-05-05T11:07:04.010 に答える
0

これは、別のデータ構造 (ステップ数を追跡できるもの) で実行できると思いますか?

通常、Floyd-Warshall は接続行列 (行列 [j][k] はノード j と k の間の距離を表す) で行われるため、その行列を整数にする代わりに、2 つの整数を持つ構造体にすることができます: 距離2 つのノード間のステップ数とそれらの間のステップ数。

私が何を意味するかを説明するために、C++で何かを書きました:

#define INFINITY 9999999

struct floydEdge
{
    int weight;
    int steps;
};

floydEdge matrix[10][10];

int main()
{
    //We initialize the matrix
    for(int j=0;j<10;j++)
    {
        for(int k=0;k<10;k++)
        {
            matrix[j][k].weight=INFINITY;
            matrix[j][k].steps=0;
        }
    }

    //We input some weights
    for(int j=0;j<10;j++)
    {
        int a, b;
        cin>>a>>b;
        cin>>matrix[a][b].weight;
        matrix[b][a].weight=matrix[a][b].weight;
        matrix[a][b].steps=matrix[b][a].steps=1;
    }

    //We do the Floyd-Warshall, also checking for the step count as well as the weights
    for(int j=0;j<10;j++)
    {
        for(int k=0;k<10;k++)
        {
            for(int i=0;i<10;i++)
            {
                //We check if there is a shorter path between nodes j and k, using the node i. We also check if that path is shorter or equal to 4 steps.
                if((matrix[j][k].weight > matrix[j][i].weight + matrix[i][k].weight) && (matrix[j][i].steps+matrix[i][k].steps<=4))
                {
                    matrix[j][k].weight=matrix[k][j].weight=matrix[j][i].weight + matrix[i][k].weight;
                    matrix[j][k].steps=matrix[k][j].steps=matrix[j][i].steps+matrix[i][k].steps;
                }
                //If the path is not shorter, we can also check if the path is equal BUT requires less steps than the path we currently have.
                else if((matrix[j][k].weight == matrix[j][i].weight + matrix[i][k].weight) && (matrix[j][i].steps+matrix[i][k].steps<matrix[j][k].steps))
                {
                    matrix[j][k].weight=matrix[k][j].weight=matrix[j][i].weight + matrix[i][k].weight;
                    matrix[j][k].steps=matrix[k][j].steps=matrix[j][i].steps+matrix[i][k].steps;
                }
            }
        }
    }
    return 0;
}

私はこれが完全に機能すると信じています（ただし、完全にはわかりません）（常にすべてのノード間の最短パスを提供します）。試してみて、教えてください！

于 2014-05-03T22:49:14.520 に答える