問題タブ [floyd-warshall]

私は、フロイド・ウォーシャルの有用性を視覚的に示すためのいくつかのアイデアを求めています。これまでのところ、ランダムグラフを生成して、ユーザーが開始/終了を選択し、最短パスを強調表示できるようにすることしか考えられません。パスファインディングの有用性を示す、もっと楽しくて簡単なデモンストレーションは何ですか？

対称隣接行列があることが保証されている場合、Floyd-Warshallの実行時間の定数係数を下げる最適化はありますか？

私はこのロジックを使用して、隣接行列で何が起こっているのかを理解しようとしていますが、abcd の間隔についてどこに書かれているのか非常に混乱しています.....

ここで何が起こっているのか誰か説明できますか?

ありがとうございます (Java としてタグ付けされているのは、これが実証された言語であるため、誰かがコード例を投稿した場合、その言語であることがわかります)

http://compprog.wordpress.com/2007/11/15/all-sources-shortest-path-the-floyd-warshall-algorithm/

コードは次のとおりです。

大学の課題があり、すでに Dijkstra と Bellman-Ford をうまく実装していますが、これについては困っています。すべて問題ないように見えますが、正しい答えが得られません。

コードは次のとおりです。

私が作成したこのグラフの例を使用しています:

これは、6 つの頂点 (1 から 6) と、重み 4 の 7 つのエッジ (1,2) があることを意味します。

誰かがさらに情報を必要とする場合は、このコードを見てエラーを見つけられないことにうんざりしています。

フロイドのアルゴリズムを使用してすべてのペアの最短経路行列を計算するようにグラフの実装を変更しています。グラフには、隣接リンクリストとマトリックスの実装の両方があります。今のところ、このアルゴリズムに必要な隣接行列を使用しています。

私の質問は、weight_matrix要素を参照して比較できるようにするにはどうすればよいですか？Objectマトリックスにあるエッジクラスは次のとおりです。

まず、ちょっとした背景: 基本的なグラフ アルゴリズム (Dijkstra、Floyd-Warshall、Bellman-Ford など) を備えた単純なグラフ クラスを作成して、今後のプログラミング コンテストのリファレンス シートとして使用する作業を行っています。

これまでのところ、機能するバージョンの Floyd-Warshall がありますが、欠点は、これまでのところ、最短パスではなく、2 つのノード間の最短距離の値しか得られないことです。できれば、別の関数を呼び出して再構築するのではなく、アルゴリズム自体の中でパス構築を行いたいと思います。

私が使用しているデータ構造に関する情報は次のとおりです。

vector< vector<int> > graph //contains the distance values from each node to each other node (graph[1][3] contains the length of the edge from node #1 to node #3, if no edge, the value is INF

vector< vector<int> > path //contains the "stepping stones" on how to reach a given node. path[st_node][end_node] contains the value of the next node on the way from end_node -> st_node

私が使用しているグラフデータの例は次のとおりです。

「パス」変数に入れる必要がある値は次のとおりです (各ノードから Dijkstra を実行して取得します)。

アルゴリズムに現在使用しているコードへのリンクは次のとおりです: (PasteBin 経由)。

どんな助けでも大歓迎です！

編集:ウィキペディアのコードを使用してパス マトリックスを生成しようとしましたが、結果は次のとおりです。

それはちょっと機能しますが、「単一の」ステップを表すことに関しては問題があります。たとえば、ノード 0 からノード 1 へのパスはどこでも定義されていません。（それでも、提案してくれたNali4Freedomに感謝します）

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

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

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

Floyd-Warshall アルゴリズム (すべてのペアの最短パス) を実装しようとしています。以下のコードでは、いくつかの数字を入力すると、最後の数字が入力として表示されます。私はコードが完全ではないことを知っています。

各 i と j の最短パスを出力するにはどうすればよいでしょうか? または、このコードを完成させるために私に何をするように提案しますか? ありがとう。

このアルゴリズムを Prolog でプログラムしたいのですが、まずグラフのリストから行列を作成する必要があります。私は以前にこれを行ったことがありますが（あなたの何人かの助けを借りて）、リストのリスト内に保存する方法がわかりません（プロローグの場合はこれが最善のアプローチだと思います）。そこから続けられると思います (各アルゴリズムにトリプル for ループを使用)。プログラムのロジックは私にとって難しくありませんが、データを操作する方法です。お手数をおかけして申し訳ありませんが、よろしくお願いします！

私のマトリックスジェネレーター：

どうやら私の先生は、何かを学ぶ時間がなくても（十分な例も）先に進むべきだと信じているので、今度はフロイド-ワーシャルとワーシャルのアルゴリズムをclispで作成する方法を知る必要があります。

私がプロローグで行ったように、私の問題はグラフから隣接行列を生成することです。この場合、それはリストのリストになります。例：

それは生成するはずです：

私はこれを持っています：

どんな助けでも大歓迎です。

また、ちょっとオフトピックです。自分の質問を解決できた場合、質問に答えるために自分自身に返信する必要がありますか？