5

私は、パスファインディングの形式を実装するように任命されました（コースワーク@大学）。さて、仕様では、検索するノードの数に制限があるため、ブルートフォースを実装することもできます（最初、途中で2つ、最後）が、このコードを再利用して、ダイクストラを実装するようになりました。アルゴリズム。

私はウィキペディアで疑似を見たことがあり、友人も私のためにいくつか書いていますが、それは意味がありません。アルゴリズムは非常に単純に見え、それを理解することは私にとって問題ではありませんが、私はそのようなことを実現するコードを視覚化することはできません。

何か提案/ヒントはありますか？

いくつかの混乱のために編集してください：
はい、ターゲットノードとソースノードがあります。
後でコードを再度使用したいので、「2つの中間停止のみ」の場合ではなく、一般的な場合にダイクストラを実装しようとしています。それ以外の場合は、ブルートフォース実装を作成するだけです。
私が少し問題を抱えている特定の問題は、それらが最適になる可能性がある場合に備えて、次善の半分の形式のパスを保存することです。特定のノードにアクセスしているときに、そのノードを通過するすべての接続を更新する方法がわかりません。
さらに編集：
今すぐいくつかの答えを調べて、試してみてください。

本当に編集：深刻な問題について言及するのを忘れました。これは、任意の2つの頂点間で最大UINT_MAXの異なる距離を持つことができるということです。ごめん。実際、私がこれに対処するのを忘れたという事実は、おそらくそもそもひどい問題の原因ですが、解決策は、幸いなことに、最短のものを選ぶことは私には明らかです。他の人の距離変数の疑似が私の可変距離を考慮していなかったのも不思議ではありません。

4

6 に答える 6

8

ダイクストラのアルゴリズムの概要は次のとおりです。

距離がゼロのソース頂点を除いて、すべての頂点の優先度（距離）が無限大である優先度キューにすべての頂点を貼り付けます（ソース頂点はそれ自体からゼロ単位の距離ですよね？ ）。

優先キューをポップします。削除された頂点は、ソースからの距離が最も短い頂点です。明らかに、キューからポップされた最初の頂点がソースです。そのポップされた頂点をvと呼びます。

vの各ネイバーを見てください。それらはすべて、vの距離よりも大きい距離になります（そうでない場合は、すでにキューからポップされているはずですよね？）。vの距離が3で、vに3つの隣接距離x （ソースからの距離：5）、y（ソースからの距離：10）、z （ソースからの距離：無限大）があるとします。

ここで、vからの各隣接距離を調べます。それらがx -3、y -2、z -4であるとしましょう。これは、ソースからvを通過するxまでのパスの距離が|であることを意味します。v | + 3（3 + 3 = 6）、yの距離は5（3 + 2 = 5）、zの距離は7（3 + 4 = 7）です。

xからvまでのパスは、xへの現在の最短パスよりも長いため、無視します。ただし、vを通過するyとzへのパスは、以前の既知の最短パスよりも短いため、更新します。

すべての頂点を通過するまで、これを続けます。各ポイントで、優先キューから最小値をポップすると、その頂点への最短パスが見つかったことがわかります。これは、可能な短いパスがv 's未満の距離で頂点を通過する必要があるためです。つまり、すでにポップされているはずです。キューからのそれ。

于 2010-05-24T18:35:08.873 に答える
3

かなり激しい問題のようなものを書いたことがない場合は、C++でDijkstaのアルゴリズムを実装します。ウィキペディアのページを読んだら、ここにあなたが始めるためのいくつかのアイデアがあります。

struct Vertex {
    int id;
    std::vector<int> neighbors;
    int dist_from_source;  // need some sentry value for "infinity"
    int prev;  // need some sentry value for "undefined"
};

これは、擬似コードの最初の数行に基づいています。Aは、2つの頂点間の距離を識別するための何らかの方法と一緒に使用Graphできます。std::vector<Vertex>

8     u := vertex in Q with smallest dist[]

この行は、std::make_heap（後で説明するpriority_queueではなく）の必要性を示しています。何かを追加したり削除したりする必要があるため、これ用に別のベクトルを作成します。dist_from_source頂点をヒープの一番上に最も低くする述語を提供する方法を調べてください。

12      for each neighbor v of u: // where v has not yet been removed from Q.

を使用しない理由は次のとおりpriority_queueですQ。vがまだにあるかどうかを確認する必要がありますQ。priority_queueではそれができません。

13        alt := dist[u] + dist_between(u, v)

ここで、に付属の距離関数が必要ですGraph。グラフデータがどのように定義されているかを言わなかったので、ここではあなた自身でちょっとしています。

17      return dist[]

この行は、最短パスを生成するために必要なデータを返すことを意味します。これは基本的に、すべての頂点が入力されている頂点のセットprevですdist_from_source。

于 2010-05-24T19:41:48.933 に答える
1

私がOPに詰め込んだウィキペディアの記事のリンクは、アニメーションのグラフィックとともに、非常に明確で簡潔な説明を提供します。

欠落している可能性のある重要な点（？）は、アルゴリズムの各ステップで、「現在の」ノードに接続されている各ノードへの最短パスを更新する可能性があることです。4ノードの「ダイアモンド」の場合、Aが開始で、Dが終了の場合、最初にBとCまでの距離を計算し、次にBからAからDまでの距離を計算し、次にCを介して計算します。 Cを通るパスは短く、「AからDへの最短パス」はCを通ります。Cを通るパスが長い場合、最短パスはBを通ります。これは明らかに（？）より複雑なネットワークに拡張する必要があります。

OPの実際の編集について： 2つのノード間に接続がいくつあるかは関係ありません。確かに、それがアルゴリズムのポイントです。考えられるすべてのパスを介してすべての接続を確認してください。ノードAとノードBが2つの道路で接続されていて、最短の道路が必要な場合は、長い道路を気にせずに捨ててください。問題に関係がないとわかっているデータは常に破棄するようにしてください。

于 2010-05-24T18:28:18.670 に答える
1

最初に必要なのは、グラフを表現する方法です。通常、これはvertexオブジェクトのコレクションであり、それぞれに隣接リストが含まれています。C ++では、これは他の頂点へのポインタのリストである可能性があります。頂点がLessThanComparableであることを確認してください。たとえば、それぞれに一意のID番号を付けることができます。

そうすれば、ウィキペディアのコードの方が理にかなっているはずです。のような擬似コードがあるたびにdist[v]、を使用する必要がありますmap<VertexIdNumber, double>。

于 2010-05-24T18:28:33.547 に答える
0

私が少し問題を抱えている特定の問題は、それらが最適になる可能性がある場合に備えて、次善の半分の形式のパスを保存することです。特定のノードにアクセスしているときに、そのノードを通過するすべての接続を更新する方法がわかりません。

アルゴリズムを少し誤解しているのではないかと思います。ダイクストラは、距離の昇順でノードを探索することによって機能します。したがって、永続的にラベル付けされているノードまでの最小距離と最適なパスを見つけることが保証されます。

通常、アルゴリズムの実行時にパスを明示的に保存することはありません。代わりに、グラフ上にスパニングツリーを構築していると考えてください。そのため、そのツリーの各ノードに到達する方法は1つしかありません。各ノードに対して保存する必要があるのは、距離ラベルとその親だけです。検索中に各ノードを最初に表示するときに、暫定的にラベルを付けます。後でそれへのより良いルートを見つける可能性がありますが、その時点で更新する必要があるのは、その単一ノードの距離と親ラベルだけです。

目的地に恒久的にラベルを付けたら、停止して、親ラベルを上に移動してソースに戻ることで、目的地への最適なルートを取得できます。

お役に立てば幸いです:)

于 2010-05-24T23:00:28.270 に答える
-2

この回答はあなたには遅すぎるかもしれませんが、他の人の助けになる場合に備えて提供します。

まず、次のことを明確にする必要があります

  1. ノード間のエッジの重みは異なります
  2. グラフは有向または無向

大学でそのようなアルゴリズムを勉強してから25年になりますが、記憶から、ウォーシャルアルゴリズムは行列法で実装する方が簡単です。あなたはここを見るかもしれません：www.ugrad.cs.ubc.ca/~cs490/Spring05/notes/graph_part3.pdf]。

于 2010-06-05T00:33:45.917 に答える