問題タブ [shortest-path]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - グラフの最小パスとは?
グラフ理論では、最小距離 (ダイクストラのアルゴリズムが検出する) と最小パス (それが何であるかはわかりません) の違いは何ですか?
networking - グラフの画像/グラフィックの生成
ネットワーク全体の最短パス アルゴリズムに取り組んでいるときに、ネットワークの全体像を生成したいと考えています。ノード (円)、リンク (線)、リンクを通過するコスト (リンク線の中央の数字)、およびリンクの容量 (それが表すノードの横のリンク線の数字) を表現したいと思います。写真の中の。この画像の作成を自動化するのに役立つライブラリ/ソフトウェアはありますか?
これは、Visio または描画アプリケーションで手動で行うことができますが、ネットワークを変更/微調整するときにコードから生成したいと考えています。
php - ノードが配列内の他のノードにランダムにリンクされた線形配列、最短経路
情報: 100 ノードの配列 [ 0 .. 99 ] があります。各ノードは、任意の数のリンクされたノードを持つことができます。
eg1, 0 は 5、10、15、20 にリンクします。eg2, 1 は 30、40、50 にリンクします。eg3 など。
100 個のノードすべてに少なくとも 1 つのリンクされたノードがあり、ノードは誰がそれらにリンクしているかを知りません。
質問: START と END が指定されている場合、最短のリンク パスを見つけるにはどうすればよいですか。
例えば。START=5、END=80、リンクパス(例) : [5]->10->24->36->[80]?
私は Pascal や PHP を使用していますが、探しているものを理解することは [コードも役立ちます]。
c# - QuickGraph ダイクストラの例
AdjacencyGraph<string, Edge<string>>実行したいがAlgorithmExtensions.ShortestPathsDijkstraありますが、QuickGraph のドキュメントは最適ではありません。
誰かが私に従うことができる例を持っていますか?
私が Google で見つけたものはすべてオブザーバーを使用していましたが、これはAlgorithmExtension必要ありません。
c++ - 有向循環グラフのすべてのノードをカバーする最短経路を見つけるにはどうすればよいですか?
あるノードからの有向巡回グラフの最短経路の例が必要です (入力となるノードからグラフのすべてのノードに到達する必要があります)。
例があれば、C ++またはアルゴリズムで必要です。
algorithm - 無向グラフでの KSPA の提案
書き直す必要がある KSPA のカスタム実装があります。現在の実装では、修正されたダイクストラのアルゴリズムが使用されています。その疑似コードは、以下で大まかに説明されています。これは一般に、エッジ削除戦略を使用した KSPA として知られていると思います。（私はグラフ理論の初心者です）。
アルゴリズムを理解しているように、k 番目の最短パスを取得するには、各ソースと宛先のペアの間に「k-1」SPT が見つかり、1 つの SPT からそれぞれ「k-1」エッジがすべての組み合わせで同時に削除されます。明らかに、このアルゴリズムには組み合わせの複雑さがあり、大きなグラフでサーバーを詰まらせます。人々はエプスタインのアルゴリズムを提案してくれました ( http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf )。しかし、このホワイト ペーパーでは「ダイグラフ」について言及していますが、それがダイグラフに対してのみ機能するという記述は見当たりませんでした。無向グラフでこのアルゴリズムを使用したことがある人はいますか?
そうでない場合、無向グラフに KSPA を実装するための (時間の複雑さに関して) 優れたアルゴリズムはありますか?
前もって感謝します、
iphone - iPhone用ダイクストラアルゴリズム
SDK 3.0 以降、iPhone の GPS 機能を簡単に使用できますが、Google のマップの使用は明示的に禁止されています。これには 2 つの意味があると思います。
- マップは自分で用意する必要があります
- 最短ルートを自分で計算する必要があります。
最短経路の計算は長年数学者を困惑させてきましたが、Tom Tom と Google の両方が素晴らしい仕事をしているので、その問題は解決されたようです。私自身は数学者ではありませんが、ネットで検索していると、 Dijkstra Algorithmに出くわしました。このアルゴリズムを iPhone のマップのようなアプリでうまく使用した人はいますか? 私/コミュニティと共有してもよろしいですか？これは正しいアプローチですか、それとも他のオプションですか? ご検討いただきありがとうございます。
performance - Bellman–Ford 最短経路アルゴリズムの性能
Bellman - Ford アルゴリズムのソリューションをキューで実装し、そのパフォーマンスを Dijkstra アルゴリズムと比較しました。Bellman - Ford の複雑さは O(NM) であるため、両者はかなり接近していました。複雑さは最悪のケースであることはわかっていますが、それでも結果は驚くべきものでした。Bellman-Ford に関する情報を検索したところ、Sedgewick の Algorithms in Java で「実際のネットワークでは、Bellman-Ford アルゴリズムは通常、線形時間で実行される」というこのステートメントのみが見つかりました。Bellman - Ford アルゴリズムのパフォーマンス動作について説明していただけますか?