ノードのグラフ (ネットワーク) があるとします。重み付けは次のとおりです。 1. 2 つのノード間のリンクを片道移動する。2. 2 つのノード間のリンクを逆方向に移動する (これらは異なる場合があります)。3. あるリンクから別のリンクへの変更。
また、一部のノードは一方向のみです。
この場合、次の場合に最適なアルゴリズムは次のとおりです。a) 最小スパニング ツリーを見つける b) 2 つのノード間の最短ルートを見つける c) 「巡回セールスマン」パス (つまり、どこにでも行き、重複を最小限に抑える最短ルート) を見つける?
また、双方向のものを、各方向に異なる重みを持つ双方向パスではなく、2 つの単方向パスとして扱うのが最善でしょうか?
- -例 - -
3
A --<2/3>-- B --<3/2>-- C
| 1 2|3
| |
^1/4 ^4/3
| |
|3 4|
8 D --<3/5>-- E
|2
|
1 ^3/1
|
|
F
<2/3> は、左に移動する 2 と右に移動する 3 の重量を意味します。^1/4 は、1 が上に移動し、4 が下に移動することを意味します。2 つのリンク間の 1 つの数値は、リンクを変更するコストです。たとえば、AD から DF に移動するには 8 のコストがかかり、AB から BE に移動するには 2 のコストがかかります。
それが理にかなっていることを願っています...
サイモン
(ps悪い用語についてお詫びします-「リンク」、「エッジ」-好きなものなら何でも;))
重み付けの種類をよりよく説明するために、エッジが線路であり、ノードが駅であると想像してください。エッジのコストは 2 つの駅間の電車の移動時間であり、ノードのコストはインターチェンジ時間の長さです (プラットフォームがどれだけ離れているかによって、同じノードであってもエッジ間で異なる場合があります。サービスの定期性など)。