問題タブ [floyd-warshall]

例えば、

まあ言ってみれば

だから1->2->4コスト700

コストが -500 の 4 から 3 へのエッジがあった場合はどうなるでしょうか? そして、コストが 200 の 3 から 4 までの別のエッジ

だから1->2->4->3->4コスト400

700未満

???1->2->4->3->4よりも短いパスと見なされます。1->2->4

循環が許可されていないことを理解しています。これは、エッジが繰り返されないパスの例です。

頂点はどうですか？彼らが繰り返す場合、それはフロイド・ウォーソールで許容されるサイクルですか?

ある種類のサイクルを許可し、他の種類のサイクルを許可しない、さまざまな種類のアルゴリズムがあることを私は知っているからです。

誰かが私にこれを説明できますか？の質問に答えると、???1->2->4->3->4よりも短いパスと見なされます。1->2->4

よろしくお願いします。

編集：

次の図は、同じエッジを 2 回訪れる必要がないことを示しています。

私は実際にフロイドのウォーシャル アルゴリズムを実装しようとしていますが、ハードポイントに遭遇しました。シーケンスのマトリックスで最短経路を見つけようとしているときに、セグメンテーション違反が発生しました。私はこのチュートリアルに従います: floyd's warshall algorithm

124 行目以外はすべて正常に動作します。

segfault を取得する場所 (アルゴリズムの実装方法を知りたい場合を除いて、最初の部分をスキップできますが、問題は 2 番目の部分にあります):

ご清聴ありがとうございました。

フロイド ウォーシャル アルゴリズムの実装に取り​​組んでいます。異なる頂点を持つグラフにこのアルゴリズムを適用しましたが、それらのいくつかはリンクされていません。私のコードは正しい答えを得ていません。

ある頂点から別の頂点に生成される最終パスには、存在しないエッジが含まれることがあります。私の誤りは、私が無限と無限を比較したという事実から来ていると思います。私は現在それを行っています: 大きな整数は、たとえば 10000 などの無限大を表すと想定しています。10000 > 10000 + n のような状況に遭遇した場合、どうすればよいですか? n < 10000

Floyd-Warshall アルゴリズムをどのように変更して、O(V^3) 時間の計算量を維持する有向グラフの負のコスト サイクルの最短経路を見つけることができますか?

このキーエラーが何度も発生しますが、その方法がわかりません。for-in ステートメントを使用しているため、キーは確実に存在します。

エラー：

キーエラーは、ノードで最初に発生したキーにあり、毎回変更されます

カエルが川を渡ろうとしています。

彼女がジャンプできる川には3つの石があります。

彼女は、考えられるすべての経路の中から、最小の最長のジャンプにつながる経路を選択したいと考えています。

すなわち。考えられる各パスには、最長のジャンプが 1 つあります。この最長のジャンプが最小になるパスを見つける必要があります。

2 つの海岸は 10 離れており、y 軸に平行です。

各石の位置は、x 位置のリスト x=[x1,x2,x3] と y 位置の y=[y1,y2,y3] によって与えられます。

パス内の石のリスト x および y 内のインデックスのリストを介して、このパス内の最長のジャンプ (最も近い整数に丸められます) とパス自体の両方を返します。

これは、最長のジャンプを見つけるための私の python コードです。

パス自体を追跡するにはどうすればよいですか?

そして、私のコードは 3 つのネストされたループで不器用に見えます。このコードを書くためのより良い/よりエレガントな方法はありますか?