問題タブ [dijkstra]

フィボナッチ ヒープを使用したダイクストラの実装を考案しようとしています。私が理解しようとしているのは、O(logn) (削除あり) の最小距離以外に、特定のノードの隣接ノードを表すことができるかどうかです。それとも、これはフィボナッチ ヒープ構造に違反していますか? そうしないと、隣人リストとフィボナッチ ヒープを作成する必要があります。

Dijkstra のアルゴリズムと Floyd-Warshall アルゴリズムについて調べています。Dijkstra は 1 つのノードから他のすべてのノードへの最適なルートを見つけ、Floyd-Warshall はすべてのノードのペアリングの最適なルートを見つけることを理解しています。

私の質問は、すべてのペアリング間の最適なルートを見つけるために、すべてのノードで実行すると、ダイクストラのアルゴリズムがフロイドのアルゴリズムよりも効率的であるかということです。

Dijkstra の実行時間は O(E + VlogV) で、Floyd の実行時間は O(V ³ ) です。ダイクストラが失敗した場合、この場合のランタイムはどうなるでしょうか? ありがとう！

エントリ 0、1、2 を持つ長さ 12 のベクトルの空間を検索しています。たとえば、そのようなベクトルの 1 つは
001122001122 です。約 1000 個の良いベクトルと約 1000 個の悪いベクトルがあります。悪いベクトルごとに、最も近い良いベクトルを見つける必要があります。2 つのベクトル間の距離は、一致しない座標の数です。優れたベクトルは特にうまく配置されているわけではなく、それらが「優れている」理由はここでは役に立たないようです。私の主な優先事項は、アルゴリズムが高速であることです。

単純な徹底的な検索を行うと、約 1000*1000 の距離を計算する必要があります。かなり頭が固いようです。

最初に適切なベクトルを使用して Dijkstra のアルゴリズムを適用すると、空間内のすべてのベクトルに対して最も近いベクトルと最小距離を計算できるため、悪いベクトルごとに簡単なルックアップが必要になります。しかし、空間には 3^12 = 531,441 個のベクトルがあるため、事前計算は 50 万回の距離計算になります。あまり節約できません。

より良い方法を考えるのを手伝ってもらえますか?

編集: 人々が彼らを「良い」ものにする理由を真剣に尋ねたので: 各ベクトルは、立方体の 3D 配置の 2D 画像である 6 つの正三角形の六角形の図の説明を表します (一般化された Q-bert を考えてください)。正三角形は、立方体 (45-45-90) の面の半分であり、遠近法に傾いています。座標のうち 6 つは三角形の性質 (知覚される床、左の壁、右の壁) を記述し、6 つの座標は辺の性質 (知覚される連続性、知覚される 2 種類の不連続性) を記述します。1000 個の適切なベクトルは、立方体を遠近法で見たときに確認できる六角形を表すものです。検索の理由は、三角形でいっぱいの 16 進マップにローカル補正を適用することです...

ダイクストラアルゴリズムでは負のエッジが許可されていないのに、ベルマンフォードアルゴリズムでは負のエッジサイクルが許可されているのはなぜですか?

大学のデータ構造とアルゴリズムのクラスでは、論文で提示されたアルゴリズムを実装する必要があります。論文はここにあります。だから私はアルゴリズムを完全に実装しましたが、まだいくつかのエラーが残っています（しかし、それが私がこの質問をしている理由ではありません。これまでの実装方法を確認したい場合は、ここで見つけることができます）

Stackoverflowについて質問する本当の理由は、割り当ての2番目の部分です。アルゴリズムを改善する必要があります。私はいくつかの方法を考えていましたが、それらはすべて理論的には良いように聞こえますが、実際には実際にはうまくいきません。

• ソースノードとエンドノードの間に線を引き、その線の中央に最も近いノードを検索し、「パス」を再帰的に2つに分割します。基本的なケースは、単一のダイクストラが計算を行う場合、より小さなグラフになります。これは実際には現在のアルゴリズムの調整ではありませんが、これが最適なソリューションを提供しないことは明らかであると考える人もいます。
• エンドノードを指すエッジに高い優先度を与えることにより、アルゴリズムに方向性を与えるようにしてください。これも最適ではありません。

だから今、私はすべてアイデアがなく、ここの誰かが私に可能な調整のための少しのヒントを与えることができることを望んでいます。アルゴリズムを実際に改善する必要はありません。彼らが私たちにこれを行うように頼んだ最初の理由は、背後にあるものを知らずに論文からアルゴリズムを実装するだけではないからだと思います。

（Stackoverflowがこの質問をするのに適切な場所でない場合は、お詫びします:)）

アルゴリズムの簡単な説明：アルゴリズムは、どのノードが有望に見えるかを選択しようとします。約束するということは、彼らが最短経路に横たわる可能性が高いということです。ノードがどの程度有望であるかは、その「リーチ」によって表されます。パス上の頂点の到達範囲は、始点と終点までの距離の最小値です。グラフ内の頂点の到達範囲は、すべての最短経路での頂点の到達範囲の最大値です。ダイクストラのアルゴリズムでノードが優先キューに追加されているかどうかを最終的に判断するために、test（）関数が追加されています。

Harm De Weirdt

ダイクストラの概念とは異なる、どのようなルーティング アルゴリズムが存在しますか?

ダイクストラ (および A*、D*、ベルマン フォージなど) は、次の概念を使用します。既知のノードから最適なノードを取得し、これを展開して、結果を既知のノードに保存します。

基本的に異なる概念はありますか?

ですから、これはCSでMSCを取得している人にとっては古典的な質問だと思います。

N要素があり、距離もあります。次の距離の要素が3つあるとします。対称なので

マトリックスのように見えます：

私の質問は次のようになります：

• これを効率的に保存するにはどうすればよいですか（どのデータ構造）
• 距離の合計が最小であるリンクリストを取得するための最も効率的な方法は何ですか

この場合、最良は

その他の場合：

これにはBFSが適しているのではないかという印象を受けました。アマゾンの本でさえ、英語のドキュメントへのリンクは良いです...

ダイクストラまたはベルマンフォードのアルゴリズムを使用して、特定の頂点に移動した場合にエッジの一部が影響を受けるグラフの最短経路を見つけるにはどうすればよいでしょうか。そのため、影響を受けるエッジの長さは、元の長さよりも長くなったり短くなったりします。

このダイクストラ アルゴリズムの Java コードを以下に示します。コードをダウンロードしました。このプログラムに変更を加えて、データをファイルに保存し、ソース コードに入れるのではなく読み込みたいと考えています。これを行う最良の方法は何ですか？

コードはhttp://en.literateprograms.org/Special:Downloadcode/Dijkstra%27s_algorithm_%28Java%29 [2011 年 1 月 6 日に最終アクセス] に基づいています。

簡単なグラフ形式のtxtファイルから、頂点とエッジのオブジェクトを作成したいと思います。ここのプログラマーの1人は、ダイクストラアルゴリズムのデータを格納するために簡単なグラフ形式を使用することを提案しました。

問題は、現時点では、重み、リンクなどのすべての情報がソースコードに含まれていることです。そのための別のテキストファイルを用意して、プログラムに読み込みたいです。

スキャナーを使用してテキストファイルをスキャンするためのコードを使用することを考えました。しかし、同じファイルから別のオブジェクトを作成する方法がよくわかりません。助けてもらえますか？

ファイルは

ダイクストラアルゴリズムコードは

ダウンロード元：http ：//en.literateprograms.org/Special：Downloadcode / Dijkstra％27s_algorithm_％28Java％29 * /

ファイルをスキャンするためのコードは