問題タブ [floyd-warshall]

私はフロイドのアルゴリズムを編集しているので、k が最高の中間頂点である各 Dk の代わりに、k が最大パス長です。最終的にはフロイドのものと同じ出力になりますが、すべてのサブイテレーションは異なる可能性があります。たとえば、0、1、2、3 の 4 つの頂点がある場合、最大長が K である 0 から 3 までの最も安価なパスを見つけたいとします。グラフは有向であると想定されます。

したがって、k=2 の場合、すべての矢印がエッジ/パスを示す 0->3...0->1->3...0->2->3 しかチェックできません。k=3 の場合、0->3...0->1->3...0->1->2->3...0->2->3... しかチェックできません。 0->2->1->3 など...

これの実装を理解するのに助けが必要で、フロイドのアルゴリズムは別として、どこから始めればよいかわかりません。

私のアルゴリズム（floyd-warshall）が最短経路を計算するときに渡された頂点をリストダウンする方法を理解できないようです。再帰を使用する必要があると言われましたが、再帰の使用方法がわかりません。疑似コード/例を教えてください。大歓迎です!

任意の頂点間のすべての可能なパスに沿って、一連の最小エッジ重みの最大値をどのように見つけることができます(u,v)か？

私はフロイド・ウォーシャルの修正を考えていましたか？

最小エッジウェイトは1です

最小エッジウェイトは3です

したがって、結果は次のようになります。max(1, 3) = 3

Skiena のアルゴリズムの本には、Floyd Warshall アルゴリズムの次の説明が含まれています。

Floyd-Warshall のすべてのペアの最短経路は、O(n ³ ) 時間で実行されます。これは、漸近的に、ダイクストラのアルゴリズムへの n 回の呼び出しよりも優れていません。ただし、ループは非常にタイトで、プログラムは非常に短いため、実際にはより適切に実行されます。これは、隣接リストよりも隣接行列でうまく機能するまれなグラフ アルゴリズムの 1 つとして注目に値します。

太字の部分が真である理由を誰か詳しく説明してもらえますか?

について

'a'とは何を表し、aの2つの次元のそれぞれは何を表しますか？

'n'は何を表しますか？

場所のリストと、それらの場所間の接続のリストがあり、相互に接続されている接続間の距離を計算しました。次に、任意の2つの場所（フロイド）間の最短経路を見つける必要がありますfloyds(int a[][100],int n)が、場所の配列、都市の辞書、および接続の配列に適用する方法を理解する必要があります。

参考までに-ObjectiveCを使用-iOS。

フロイドのアルゴリズムを実装しようとしています。私のコードには、理解できない問題があると思います。出力は異なります。それらは、いくつかの小さなものが欠けているだけです。以下のコードには、入力、出力、および元の出力も含まれています。少しでもお役に立てば幸いです。

*/

Floyd-Warshall アルゴリズムを実装しました。それらの行列によると、2 つの場所の間の最短経路とその距離について、正しい結果を得ることができます。私の質問は、i から j までの最短距離を出力する方法です。私はいくつかの調査を行い、そのようなアルゴリズムを見つけました。誰かが私にそれがどうあるべきか、またはどのように機能するかを説明できますか、または他の提案を言うことができますか?

ノード/頂点のすべてのペア間の最短パスの距離と、これらの各ペア間の単一の最短パスを返すために、Floyd-Warshall を実装しました。

ノードのすべてのペアに対して、最短で結ばれている複数のパスがある場合でも、すべての最短パスを返すようにする方法はありますか? （私が時間を無駄にしているかどうか知りたいだけです）

私は3つを研究してきました、そして私はそれらからの私の推論を以下に述べています。私がそれらを十分に正確に理解したかどうか誰かに教えてもらえますか？ありがとうございました。

1. ダイクストラのアルゴリズムは、単一のソースがあり、あるノードから別のノードへの最小パスを知りたい場合にのみ使用されますが、このような場合は失敗します

2. Floyd-Warshallのアルゴリズムは、すべてのノードのいずれかがソースになる可能性がある場合に使用されるため、任意のソースノードから任意の宛先ノードに到達するための最短距離が必要です。これは、負のサイクルがある場合にのみ失敗します

（これは最も重要なものです。つまり、これは私が最も確信が持てないものです:)

3.Bellman-Fordは、ソースが1つしかない場合、ダイクストラのように使用されます。これは負の重みを処理でき、その動作は1つのソースを除いてFloyd-Warshallと同じですよね？

確認する必要がある場合、対応するアルゴリズムは次のとおりです（提供：ウィキペディア）。

ベルマンフォード：

ダイクストラ：

フロイド-ウォーシャル：

基本的に、Floyd-Warshall アルゴリズムを使用するポイントは、接続されたグラフ内の 2 つのノード間の最短経路を決定することです。私がやろうとしているのは、単に最短経路を見つけるのではなく、均等な重みでもある最短経路が欲しいということです。

たとえば、これは Floyd-Warshall アルゴリズムの単純な実装です。

次の入力があるとします。

次の出力が必要です（フォーマットは無視してください。各ステップで「奇数行列」を見つける方法が必要です）

私のコードが現在行っていることは、個別の「奇数」と「偶数」の各マトリックスで表される最適な重みを取得することです。

私の理解不足は、最適値が反対の行列 (奇数/偶数) にある場合に、「奇数」行列と「偶数」行列がどのように非最適値になるかということです。それを行うには、ある種のループまたは再帰が必要になるように思えますが、これをどのように達成するかについてはわかりません。