問題タブ [dijkstra]

Javaを使用して.osmマップ上の最短パスを見つけるための単純なダイクストラのアルゴリズムを実装しました。

.osmファイルから作成されたグラフのパスファインディングは非常にうまく機能します。しかし、ユーザーの現在の場所や目的地がこのグラフのノードではない場合（生の座標のみ）、パスファインディングを機能させるために、これらの座標をグラフに「リンク」するにはどうすればよいですか？

「現在のロケーションノードに最も近いものを見つけて直線を描く」という単純で単純な解決策は、現実的ではないようです。添付の写真のような状況になった場合はどうなりますか？（UPD）

ここでの問題は、「スマートな」パスファインディングアルゴリズム（ダイクストラのような）を開始する前に、現在の位置をグラフに「リンク」することですが、これは、地理的座標とこの式は「パスファインディング」ではありません-障害物やノードのタイプを考慮に入れることはできません。

言い換えると、Bがグラフのノードであり、Aがノードではない場合、AとBの間の最短経路をどのように見つけるのでしょうか。

この問題に対する他の解決策について聞いたことがありますか？

これが機能することを確認したいだけです。ダイクストラのアルゴリズムを使用して最大のパスを見つけることができますか？最初に距離を-1のようなものに初期化してから、relaxサブルーチンを変更して、それよりも大きいかどうかを確認する必要がありますか？

これは、負の重みがない問題の場合です。

これが実際の問題です。

電話網の図が与えられたとします。これは、頂点がスイッチの中心を表し、エッジが2つの中心間の通信回線を表すグラフGです。エッジは、最も低い帯域幅のエッジの帯域幅によってマークされます。ダイアグラムと2つのスイッチセンターaとbが与えられた場合、aとbの間のパスの最大帯域幅を出力するアルゴリズムを与えます。

これは機能しますか？

編集：

私はこれを見つけました：

ヒント：基本的なサブルーチンは、ダイクストラのサブルーチンRelaxと非常によく似ています。エッジ（u、v）があると仮定します。min {d [u]、w（u、v）}> d [v]の場合、d[v]をmin{d [u]、w（u、v）}に更新する必要があります（aからuからvへの帯域幅はmin{d[u]、w（u、v）}であり、これは現在の帯域幅よりも大きくなります）。

初期化時にはすべての距離が無限大であるため、それが何を意味するのか正確にはわかりません。だから、これがどのように機能するのかわかりません。手がかりはありますか？

負の重みを持つ具体的な例は思いつきません。2 つの家の間の距離がマイナスになることはありません。時間を遡ることはできません。エッジの重みが負のグラフを作成するのはいつですか?

Bellman Ford アルゴリズムはもともと ARPANET でルーティングを処理するために使用されていたことがわかりました。考えすぎかもしれませんが、簡単な例を教えてください。

タイトルが言ったように、私は与えられたグラフのノードのすべてのペア間の距離を見つけるアルゴリズムを実装しようとしています。しかし、もっとあります:(あなたを助けるかもしれないもの）

• グラフは重み付けされていません。すべてのエッジの重みが1であると見なすことができることを意味します。
• |E| <= 4*|V|
• グラフはかなり大きいです（最大で約144の深さ）
• グラフは
• サイクルがあるかもしれません
• 私はPythonでコードを書いています（アルゴリズムを参照する場合は、コードもいいでしょう:)）

ジョンソンのアルゴリズム、フロイド-ワーシャル、およびすべてのペアのダイクストラについて知っています。ただし、これらのアルゴリズムは、グラフに重みがある場合に適しています。

これらのアルゴリズムは重み付きグラフを対象としているため、私の場合により良いアルゴリズムがあるかどうか疑問に思いました。

ありがとう！

最短経路プログラムを作成しようとしていますが、グラフについて質問があります。最初にグラフを描くことになっていますか？どのノードが隣人であるかを他にどのように定義しますか???

私は、一度に 1 つの頂点を実行するのではなく、OpenMP を使用して複数のスレッド間で計算を分割し、特定のグラフ内のすべての頂点の最短パスを計算する小さなプログラムに取り組んできました。私の現在の実装は機能していますが、グラフがプログラムにハードコーディングされないように、「頂点1頂点2ウェイト」形式のファイルからグラフデータを読み取ることができるようにしたいと考えています。

ソースはこちら: http://pastebin.com/bkR7QysB

次のようにコンパイルされます。

次のデータを入力として使用します。

私の出力は次のとおりです。

これは明らかに間違っています。頂点からグラフ内の他のすべての頂点への最短パスを出力することになっていますが、ここでは、それ自体への最短パス (常に 0) と、直接隣接する頂点の 1 つだけへのパスのみを出力しています。隣人。グラフをまったくトラバースしていません。ただし、最も奇妙な部分は、GraphTest.cpp の末尾近くにある巨大なブロックのコメントを外し、ファイル処理コードをコメント アウトして、グラフ データがプログラムにハードコードされるようにすると、すべて正常に動作することです。

正直なところ、ここで何が起こっているのかわかりません。私が考えることができる唯一のことは、どこかがあまりにも早く範囲外になり、グラフオブジェクトの動作が奇妙になるということですが、それが本当なら、両方の出力が間違っているはずです...私より賢い人が実行できることを願っていますこれで、何が悪かったのかを理解するのに役立ちます。

負の重みでダイクストラのアルゴリズムを使用できますか？

止まる！「2点間を際限なく飛び越えて、無限に安い道をたどることができる」と思う前に、私は一方通行の道をもっと考えています。

このアプリケーションは、ポイントのある山岳地帯になります。明らかに、高から低に移動することはエネルギーを消費しません、実際、それはエネルギーを生成します（したがって、負のパスウェイト）！しかし、あなたがチャック・ノリスでない限り、再び戻ることはそのようには機能しません。

すべてのポイントの重みを負ではなくなるまで増やすことを考えていましたが、それが機能するかどうかはわかりません。

ここで、V1からV2につながる各エッジについて、V1からV2の距離（D）を設定します。また、DがV2までの現在の距離よりも小さい場合は、V2の現在の距離をDに設定し、V2の前身をV1に設定します。

V1を最短距離（これは単に初期点）に宣言して初期化し、完了としてマークしました。

質問：V2を宣言して距離を設定するにはどうすればよいですか？