問題タブ [shortest-path]

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

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

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

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

ありがとう！

NetworkXライブラリを使用して最短経路アルゴリズムを実装したいと思います。私の場合、重み関数は他のエッジ属性から値を導き出します。重みは計算値であるため、他の属性が変更されたときに値を更新するなどの複雑さを避けるために、追加の属性として保存したくありません。ただし、 NetworkXのアルゴリズムAPIでは、エッジデータキーとして重みが必要なようです。

それで、値を保存しないことは可能かどうか疑問に思いましたか？私の理想的なケースは、アルゴリズムにカスタムの重み関数を指定することです。

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

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

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

フィボナッチ ヒープを使わずに Dijkstra と Sedgewick-Vitter アルゴリズムを実現する必要があります。ダイクストラ フル インターネットに関する情報ですが、疑似コードや Sedgewick-Vitter アルゴリズムの例は見つかりませんでした。McHugh の Algorithmic Graph Theory book にいくつかの情報があることがわかりましたが、無料の pdf は見つかりませんでした。では、このアルゴリズムを知っていて、情報、疑似コード、リンクを共有できる人はいるでしょうか?

乾杯！

私のアプリケーションでは、ユーザーが S を開始都市、D を目的地都市として 4 つの都市を選択して、このための API または Web サービスがあるとします。

ここでは、ユーザーが都市を 1 回だけ訪問し、出力はすべての都市をカバーすることによって A と D の間の最短経路になるはずです。誰かが他のアイデアを持っているなら、それも歓迎されます。

よろしくお願いします ムルゲン

[下部の更新 (ソリューションのソース コードを含む)]

私は、コンピューターが解決できる困難なビジネス上の問題を抱えています。

山岳地帯に沿って、長く曲がりくねった川が強い流れで流れています。川の特定の部分に沿って、非常に需要の高い特定の種類の希少な果物を栽培するのに適した環境に敏感な土地の区画があります. 畑の労働者が果物を収穫すると、果物を加工工場に運ぶために時計が刻み始めます。果物を上流または陸路または空路で送ろうとすると、非常に費用がかかります。それらをプラントに輸送するための最も費用対効果の高いメカニズムは、川の絶え間ない流れのみを動力源とするコンテナの下流にある. 私たちは 10 の加工工場を建設する能力を持っており、果物が輸送に費やす合計時間を最小限に抑えるために、これらを川沿いに配置する必要があります。果物が最寄りの下流の工場に届くまでには長い時間がかかる可能性がありますが、その時間は販売価格に直接影響します. 事実上、最も近いそれぞれの下流プラントまでの距離の合計を最小化する必要があります。植物は、果物のアクセス ポイントからわずか 0 メートルの下流に配置できます。

問題は、利益を最大化するために、川の基部から上流までの距離が 10 である 32 の果物栽培地域を見つけた場合、川のどのくらい上流に 10 の加工工場を建設する必要があるかということです。 , 40, 90, 160, 250, 360, 490, ... (n^2)*10 ... 9000, 9610, 10320?

[この問題を解決し、同様の問題と使用シナリオを作成するためのすべての作業が、ソフトウェア/ビジネス方法特許の有害性と抑圧的な性質に対する意識を高め、一般的な抵抗を生み出すのに役立つことが期待されています (これらの特許がどの程度信じられているかにかかわらず)地域内で合法であること）]

アップデート

Update1: 追加するのを忘れました: この質問は、この質問の特殊なケースだと思います。

Update2: 私が書いた 1 つのアルゴリズムは、ほんの一瞬で答えを出します。かなり良いと思います (ただし、サンプル値全体でまだ安定していません)。詳しくは後述しますが、簡単に言うと以下の通りです。植物を等間隔に配置します。すべての内部プラントを巡回し、各プラントで、問題がそのスペース内で解決されるまで、隣接する 2 つの間のすべての位置をテストしてその位置を再計算します (欲張りアルゴリズム)。したがって、1 と 3 を固定してプラント 2 を最適化します。次に、2 と 4 を固定した状態でプラント 3 を保持します...最後に到達したら、サイクルを戻して、すべての処理プラントの再計算された位置が変動しなくなる完全なサイクルに進むまで繰り返します..また、各サイクルの最後に、移動しようとします隣り合って密集し、すべてが近くにある加工工場 フルーツダンプは、遠くにフルーツダンプがある地域に移動します。詳細を変更するには多くの方法があるため、正確な答えが得られます。他にも候補となるアルゴリズムがありますが、すべてに不具合があります。[後でコードを投稿します。] Mike Dunlavey が以下で述べたように、私たちはおそらく「十分に良い」ことを望んでいます。

「十分に良い」結果とは何かを考えてみると、次のようになります。

Update3: mhum は最初に正しい正確な解を提供しましたが、(まだ) プログラムまたはアルゴリズムを投稿していないため、同じ値を生成するものを作成しました。

前後の距離を計算してから減算するよりも高速な単一のエッジを追加または削除すると、グラフの平均測地線距離がどれだけ変化するかを見つける方法はありますか?

状態が無向グラフで表されるシステムのメトロポリス モンテカルロ シミュレーションを実行しています。システムのエネルギーは、このグラフの平均測地線距離に依存します。

モンテカルロの各ステップで、グラフの変更を提案し、その変更によるエネルギーの変化を計算する必要があります。ランダムなエッジを選択して反転しているだけです (エッジが存在しない場合はエッジを追加し、存在する場合はエッジを削除します)。私が今していることは、一種のブルートフォースです。

私はむしろこれをしたい：

エネルギーの差の計算は、エネルギー自体の計算よりも大幅に高速でした。これは、指定されたエッジがはるかに高速な方法で反転された場合に平均測地線長の差を計算する方法がある場合に可能です (big-O-wise)。

これを行う方法はありますか？1 つのエッジの変更によってどのパスが影響を受けるかを予測するのは難しいことは承知していますが、運がよかったのかもしれません。:D

編集：あなたが考えているアルゴリズムに使用しなければならない表現は気にしません。時間が節約できるなら、喜んでそうします。

私のグラフは通常、一種の小さなものです (頂点の数は通常 100 未満であり、エッジの数は少数と完全に接続されたものの間で異なります)。問題は、平衡を達成するためにこのループを非常に多くのステップで繰り返さなければならず、それらが多くの非常に多くの異なる条件のそれぞれについて多くのオブザーバブルを計算することです... :(

編集 2: 個々の測地線パスやその長さは必要ありません。平均的な測地線の長さだけが必要です。

オーバーフローの皆さん、こんにちは。

加重有向グラフがあり、ルートがグラフの特定のノードであるすべてのノードをカバーする最低コスト ツリーが必要です。このノードから他のノード (外側のエッジ) への分岐の数がその最大値以下である場合、各ノードに異なる最大分岐を設定できるかどうかもわかりません。

では、読書を始めるための私のニーズに最も適したアルゴリズムは何ですか? 私はそれが十分に速いことを願っています:)

どうもありがとう ！

次に行うことを検討する

（オペレーションで）作るために何をしなければなりませんか：

myPoints には一連のポイントがありmyPoints[initialindex]、StartPosition を検討します。返される配列は、最短パスを取得するために順序付けられたポイントです。

Floyd-Warshall または Dijkstra を適用する方法がわかりません。

テキストの壁で申し訳ありませんが、それは私ができる限り簡潔です!

私は 1 つの非常に大きな有向グラフ G と、G 内からの頂点のサブセット S を持っています。私がやりたいことは、S によって誘導される G の部分グラフを見つけることです。 p と G の頂点 q で、誘導されたサブグラフのこれら 2 つの頂点の間にエッジが存在すること。これが重要です。通常の誘導されたサブグラフの問題よりも少し複雑です（私はそう思います）。

問題を解決するために私が考えることができる最も基本的な方法は次のとおりです（おそらく最も効率的ではないことを認識しています。実装するのに複雑すぎない他の提案があれば教えてください）：S内の頂点のすべてのペアについて、G でそれらの間のパスの存在をテストします。そのようなパスが存在する場合、誘導された部分グラフの p と q の間にエッジを挿入します。私の目的では、n^2 時間はそれほど悪くありません。

したがって、2 つの質問があると思います。1) 2 つの頂点間にパスが存在するかどうかを判断する最速の方法は何ですか? パスが存在するかどうかだけで、パスを知る必要はありません。さらに、この計算を高速化するためにグラフ全体に対して実行できる前処理がある場合、頂点の各ペア間でこの計算を実行する必要があるため、それは何でしょうか?

2）私が説明した誘導サブグラフのタイプを見つけるために私が提案した方法よりも速い方法はありますか？

助けてくれてどうもありがとう！