5

まず、ちょっとした背景: 基本的なグラフ アルゴリズム (Dijkstra、Floyd-Warshall、Bellman-Ford など) を備えた単純なグラフ クラスを作成して、今後のプログラミング コンテストのリファレンス シートとして使用する作業を行っています。

これまでのところ、機能するバージョンの Floyd-Warshall がありますが、欠点は、これまでのところ、最短パスではなく、2 つのノード間の最短距離の値しか得られないことです。できれば、別の関数を呼び出して再構築するのではなく、アルゴリズム自体の中でパス構築を行いたいと思います。

私が使用しているデータ構造に関する情報は次のとおりです。

vector< vector<int> > graph //contains the distance values from each node to each other node (graph[1][3] contains the length of the edge from node #1 to node #3, if no edge, the value is INF

vector< vector<int> > path //contains the "stepping stones" on how to reach a given node. path[st_node][end_node] contains the value of the next node on the way from end_node -> st_node

私が使用しているグラフデータの例は次のとおりです。

INF 10  INF INF INF INF
INF INF 90  15  INF INF
INF INF INF INF INF 20
INF INF INF INF 20  INF
INF INF  5  INF INF INF
INF INF INF INF INF INF

「パス」変数に入れる必要がある値は次のとおりです (各ノードから Dijkstra を実行して取得します)。

INF  0   4   1   3   2
INF INF  4   1   3   2
INF INF INF INF INF  2
INF INF  4  INF  3   2
INF INF  4  INF INF  2
INF INF INF INF INF INF

アルゴリズムに現在使用しているコードへのリンクは次のとおりです: (PasteBin 経由)。

どんな助けでも大歓迎です！

編集:ウィキペディアのコードを使用してパス マトリックスを生成しようとしましたが、結果は次のとおりです。

INF INF  4   1   3   4
INF INF  4  INF  3   4
INF INF INF INF INF INF
INF INF  4  INF INF  4
INF INF INF INF INF  2
INF INF INF INF INF INF

それはちょっと機能しますが、「単一の」ステップを表すことに関しては問題があります。たとえば、ノード 0 からノード 1 へのパスはどこでも定義されていません。（それでも、提案してくれたNali4Freedomに感謝します）

4

2 に答える 2

2

ハザ！

ウィキペディアのコード スニペットを追加した結果をじっと見つめていたので、別の関数を呼び出す必要なく、その結果を自分の結果に変換するアダプターを思いつきました。

// Time to clean up the path graph...
for (int st_node = 0; st_node < this->size; st_node++)
{
    for (int end_node = 0; end_node < this->size; end_node++)
    {
        int mid_node = this->path[st_node][end_node];

        if (mid_node == INF)
        {
            // There is no mid_node, it's probably just a single step.
            if (this->graph[st_node][end_node] != INF)
            {
                this->path[st_node][end_node] = st_node;
            }

        } else {
            // The mid_node may be part of a multi-step, find where it leads.
            while (this->path[mid_node][end_node] != INF)
            {
                if (this->path[mid_node][end_node] == mid_node) { break; }  // Infinite loop
                if (this->path[mid_node][end_node] == INF) { break; }   // Dead end

                mid_node = this->path[mid_node][end_node];
            }

            this->path[st_node][end_node] = mid_node;

        }   // IF mid_node
    }   // FOR end_node
}   // FOR st_node

基本的に、ノード A からノード B への移動が単一のステップ(mid_node == INF)である場合、元のグラフにエッジが存在する場合はエッジを追加することで補正します。あるいは、それが指しているノードが目的のノードへの足がかりにすぎない場合は、その先のノード(this->path[mid_node][end_node] != INF)が見つかるまで掘り下げます。

助けてくれてありがとう、大声で考えてくれる人が必要だったと思います!

于 2010-10-25T22:39:06.233 に答える
1

ウィキペディアには、良い情報と疑似コードがいくつかあります。基本的に、|V|x|V| を埋めるだけです。「next」行列。要素 i,j には、ノード i からノード j に移動するために移動する必要がある頂点のインデックスが含まれます。i から j への最短経路は、i から next[i][j] および next[i][j] から j への経路として与えられます。フルパスが得られるまで、このように再帰的にパスを分解し続けます。

于 2010-10-25T21:26:14.490 に答える