問題タブ [dijkstra]

グラフ内の任意のノードとルート/ソース間の最小距離を見つけることに興味があります。すべてのリンクには重みがあります。各ノードの親を知る必要がないため、ウィキペディアの記事previous[]に示されているを使用する必要はないと思います。あれは正しいですか？さらに、重みがすべて 1 に等しい場合、BFS を実行できますか?

それぞれに1000000の値を持つ803*803 （644 809）グラフを配置するスクリプトがあります。〜500 * 500を使用すると、すべてが正常に機能しますが、現在はクラッシュします。64MBを超えるメモリを割り当てようとします（私はまだ割り当てていません）。解決策は何ですか？どういうわけかそれを「分割」するか...？

*それはダイクストラアルゴリズムについてです

psいいえ、64MBを超えて割り当てることはできません

上記のアルゴリズムは、ウィキペディアの Dijkstra Shortest Path で言及されています。ここで理解できないのは、すべての頂点への距離を無限大に設定している間[行番号3]、9行目で割り当てu := vertex in Q with smallest dist[]ていますが、すべての距離が無限であるため(行番号3で設定されているように)どのようにして最小の距離がありえますか?

Dijkstra のアルゴリズムを Python で実装する必要があります。ただし、先行情報、長さ、未訪問/訪問の 3 つの情報を保持するには、2D 配列を使用する必要があります。私は C で Struct を使用できることを知っていますが、Python で同様のことを行う方法にこだわっていますが、可能であると言われていますが、正直に言うとわかりません

最短経路を見つけるためのダイクストラアルゴリズムは、A *アルゴリズムよりも優れていますか?

ダイクストラのアルゴリズムを書こうとしていますが、コードで特定のことを「言う」方法に苦労しています。視覚化するために、配列を使用して表現したい列を次に示します。

したがって、以下のコードに見られるように、いくつかの配列があります。

太字の部分は、私が立ち往生している場所です-アルゴリズムのこのセクションを実装しようとしています:

3. 現在のノードについて、未訪問のすべての隣接ノードを考慮し、それらの暫定的な距離を計算します。たとえば、現在のノード (A) の距離が 6 で、別のノード (B) と接続するエッジが 2 の場合、A を介して B までの距離は 6+2=8 になります。この距離が以前に記録された距離よりも小さい場合、距離
4 を上書きします。訪問したノードは二度とチェックされません。現在記録されているその距離は最終的で最小限です

私は正しい軌道に乗っていると思います。「ノードから開始し、ソースからノードまでの長さを取得し、長さが小さい場合は前の値を上書きしてから、次のノードに移動する」という言い方に固執しています

3 つの入力変数 (開始、停止、時間)を持つ次のダイクストラ アルゴリズムがあります。完了するまでに約 0.5 ～ 1 秒かかります。私のホスティング プロバイダーは、リソースの使用量が多すぎるため、キャッシュ メカニズムを実装する必要があると言っています。私の質問は、どのようにですか？

私には 3 つの変数があるため、そのうちの 1 つだけが変化すると、結果全体が異なります (時間に関する追加のステートメントがいくつかあるため、気にしないでください)。では、キャッシュメカニズムを実装する方法や最適化を行う方法は?

私は1700 個のノードを持っています。

ダイクストラのアルゴリズムを含む解決方法がわからないという問題に遭遇しました-これが私のコードです:

このコードを実行すると、次のエラーが発生します。

このエラー (アスタリスクの間のセクション) を修正する方法がわかりません。私がやろうとしているのは、コンマで区切られた一連の整数であるテキスト ファイルを読み取り、そのテキスト ファイル内のノードの数を数えることです。その後、各ノードには Node クラスの値が割り当てられます

ローワンさんはパリのウォーキングツアーを計画しています。しかし、彼は少し怠け者なので、行きたい場所をすべて通る最短経路をたどりたいと思っています。彼はバスで最初の場所に行き、最後の場所から別の場所に戻る予定なので、開始場所と終了場所を自由に選択できます。あなたは彼を助けることができますか？

入力

入力の最初の行には、訪問する場所の数 (n) が含まれています。次に、次の n 行で、訪問する各場所の座標を見つけます。次に例を示します。

3

132 73

49 86

72 111

出力

テスト ケースごとに、ある場所から別の場所への徒歩距離がユークリッド距離であると仮定して、Rowan 氏がすべての場所を訪れるために歩かなければならない最小距離を含む 1 行をプログラムで出力する必要があります。アルゴリズムは、小数点の右側に正確に 3 桁の数字を固定小数点表記で出力し、先頭にスペースを入れない必要があります。訪問する場所は最大で 12 か所あります。例

入力例:

3

132 73

49 86

72 111

出力例:

104.992

私は宿題のためにこのコードに取り組んできましたが、うまくいかず、これが最善のアプローチであるかどうか疑問に思い始めました..

問題は floyd-warshall 関数です。floydwarshall(path, n, next); の前後で path が同じです。floydwarshall(path, n, next);