0

ベルマンフォード アルゴリズムのプログラミング中に 1 つの問題に遭遇しました。これは技術的というよりも理論的な問題ですが、次のとおりです。

A、B、C、D の 4 つのポイントがあり、A から B までのコストは 3 などです。グラフは次のとおりです。

B--3--C
|     |
3     9
|     |
A--1--D

A から D を経由して C までのコストを知りたいとします10。または、A から D に移動し (コストは 1)、D から A に戻り (合計コストは 1+1=2)、A から B に移動し (1+1+3=5)、B から C に移動します (コストの合計は 1+1=2)。 1+1+3+3=8) ではあり8ません10か?

どこでも検索しましたが、私の質問に対する合理的な答えは見つかりませんでした。

編集:
A->D および D->C のパス数は 2 で、A->D の場合、D->A、A->B、B->C の場合、パスの合計数は 4 になるとしましょう。経路数が最短 (経路数 = 2) の方法を選択するか、経路数が長い (経路数 = 4) の方法を選択しますか?

4

2 に答える 2

2

viaの問題については、アルゴリズムの1回の実行は使用しません。私はそれを二度呼ぶでしょう。最初にA -> D、、次に、のためD -> Cに、それは実際には問題です。その場合、最終的なパスはこれら2つの合計です。

注：私はベルマンフォードアルゴリズムに精通していません。この答えは、パスファインディングに関する一般的な意見にすぎません。

于 2012-09-17T12:06:24.443 に答える
0

負の重みのサイクルがない場合、すべての最短パスは各頂点を最大 1 回訪れます。

于 2012-09-17T12:10:03.073 に答える