問題タブ [dijkstra]

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

乾杯！

最初に、私の英語の知識が乏しいことをお許しください。

次の問題があります: 修正順序 (例: A -> D -> F) で 2 つ以上のポイント間の最短経路を見つけなければなりません。私はダイクストラのアルゴリズムに精通しています。しかし、それは 2 つの Point 間の最短経路のみを計算します。また、TSP についても聞いたことがありますが、それも当てはまらないようです。修正順序がないためです。自分の問題を既に Web で検索しましたが、あまり人気のない問題であるか、間違ったキーワードを使用した可能性があります。

それでも、この機能をうまく提供しているルート プランナーはたくさんあるので、解決策が存在するはずです。

だから、アグロリスに名前を付けて私の問題を手伝ってくれる人、またはアドバイスをくれる人がいますか。

ご助力ありがとうございます！敬具 アンジェロ

//編集ああ、それは非常に恥ずかしいです. 私は長い間考えていたようで、実際の問題を説明できませんでした。そのようなものです：最初からしか使用できないいくつかのチケットがあります。

T1: A -> B (コスト 50) T2: B -> C (コスト 50) T3: A -> B -> C (コスト 80) 与えられたルートは A -> B -> C

ご覧のとおり、指定されたルートを 2 つの別々の問題として扱うと、総コストは 100 になりますが、明らかにチケット T3 の方が優れたソリューションです。

私のダイクストラアルゴリズムは、パスを見つけるためにうまく機能します。今、私は自分が行った道を示すために戻ってきたいと思っています. 訪問した頂点をマークし、「前」から来た頂点へのポインターを与えます。残念ながら、これらのポインターは while ループでループするときに何らかの方法で操作されるため、最後の頂点はどこから来たのかわかりません。手伝って頂けますか？

おそらく、それは私が得られないポインタの問題です。コピー コンストラクターと =operator があります。

グラフにダイクストラアルゴリズムを適用して、結果のツリーが2つの指定された頂点の間にエッジを持たなければならないような方法でMSTを見つけるにはどうすればよいですか？（例：MSTにはXとYの間のエッジが含まれている必要があります）

ありがとう

敬礼。ダイクストラは、一見単純なコードの数行でさえ、絶望的に曖昧になる可能性があると書いています。私の命を救うために今は見つけることができない少なくとも1つの作品で、彼はこの曖昧さを実証するための小さなサンプルプログラムを提供しました。誰かが私に彼の論文を指摘してもらえますか？彼はこれらの例の1つを含んでいますか？

ダイクストラのアルゴリズムをJavaで実装しようとしています（自習）。ウィキペディア（リンク）が提供する擬似コードを使用します。アルゴリズムの終わり近くで、私はする必要がありdecrease-key v in Q;ます。BinaryHeapなどでQを実装する必要があったと思いますか？ここで使用するのに適切な（組み込みの）データ型は何でしょうか？

以下は、ウィキペディアの記事の擬似コードから書いたダイクストラのアルゴリズムの実装です。約40000ノードと80000エッジのグラフの場合、実行には3〜4分かかります。それは正しい桁のようなものですか？そうでない場合、私の実装の何が問題になっていますか？

彼の影響力のある論文、Self-stabilizing systems inにもかかわらず、分散制御を読みました。ただし、自己安定化アルゴリズムがどのように機能するかはよくわかりません。私が最も興味を持っているのは、彼の k ステート マシンの「ソリューション」です。紙の密度はかなり強烈で、あまり意味がありません。このアルゴリズムは平易な英語でどのように機能しますか?

以下に記述したコードに Dijkstras Algorithm を書き込もうとしています。しかし、これを開始する方法がわかりません。オンラインの情報源から少し見直しましたが、実際に機能させる方法はまだわかりません. 私はそれを評価パスメソッドに配置することを好みます。次に、メニュー オプションでこのメソッドを呼び出し、並べ替えアルゴリズムを実行します。

ご参考までに。都市 A から都市 B への最短経路をマイルと価格で並べ替えています。

以下は私が持っているコードです。

出力は次のようになります::

シアトルからサンフランシスコまでの最短ルートは 1290 マイルです。