問題タブ [floyd-warshall]

次の問題を解決しようとしています。

私たちの銀河系には N 個の惑星があります。異なる惑星間を移動することはできますが、すべての惑星が安全なルートを介して別の惑星に結合されるわけではありません。各ルートには、光年で指定された長さがあります。あなたの仕事は、与えられた一連の惑星 T(ここで 0

入力は、N(惑星の数)、R(惑星間の安全なルートの数)、トリプル ABL 形式の R ルートで構成されます。ここで、A と B は惑星の恒星 ID を表し、L は惑星間の距離を表します。年、T（基地を設置する必要がある惑星の数）、その後に基地を設置する必要がある惑星の ID を表す T 番号が続きます。

常に ID: 0 の惑星から開始します。惑星 0 に基地を設置する必要がある場合とない場合があります。

私は演習問題を解決しようとしましたが、うまくいく解決策を得ることができましたが、遅すぎます。Floyd Warshall アルゴリズムを使用して、グラフ内の任意の 2 つのノード (惑星) 間の最小パスを取得しました。次に、基数を 0 にする必要がある最も近い惑星を見つけ、その経路を計算します。次に、この惑星を「訪れた惑星」のリストに追加し、「対象」の惑星のリストから削除します。このプロセスを最後まで繰り返しますが、今度は、ターゲットの惑星から訪問した任意の惑星に最も近い惑星を見つけようとします (それらの間の移動は無料なので、最後にどこにいたかは気にしません)。次に、距離を追加し、ターゲットから削除し、訪問済みに追加して、必要なすべてのベースを確立するまで続けます。

これは正しい出力を提供しますが、遅すぎます。

改善のためのアイデアはありますか？おそらく、ダイクストラのアルゴリズムのいくつかの変更されたバージョンですか?

Floyd Warshall アルゴリズムの「最短経路」( https://www.cs.usfca.edu/~galles/visualization/Floyd.html?hc_location=ufi ) の距離行列を作成するには、頂点としていくつかの道路と間の距離が必要です。これらの道路をエッジとして。例 (出発、目的地、距離): roads = [["Philadelphia", "New York City", 120 ], ["New York City", "Philadelphia", 97 ],[ "Millburn, "New York City", 25 ],["Morristown", "Harrisburg", 150] Python でこの行列を作成するにはどうすればよいですか?

これは構造です：

network[roads[i][0],[roads[i][1]]目的地または出発地が複数回使用されている場合、正しい解決策ではないため、距離を正しい位置に記入する方法がわかりません。

どうもありがとう！

floyd warshall アルゴリズムの疑似コードを読みましたが、 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each vertex v 3 dist[v][v] ← 0 4 for each edge (u,v) 5 dist[u][v] ← w(u,v) // the weight of the edge (u,v) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ← dist[i][k] + dist[k][j] 11 end if 距離を節約するために 1 つの dist 行列を使用するだけです。n 個の dist 行列が必要だと思います.n は頂点の数です. または、少なくとも 2 つの dist 行列が必要です. 1 つは頂点 k-1 内の現在の最短パスを格納し、もう 1 つは頂点 k 内の最短パスを格納し、最初のパスは k+1 内の最短パスを格納します。頂点内の距離に対する元の行列の k k-1?

この図は、D0、D1、D2....D(n) が必要であることを示しています

DAGの隣接リストMap<Vertex, Set<Vertex>>が与えられた場合、すべての頂点の到達可能性を計算したいと考えています (つまり、u から v へのパスがある場合)。

static Map<Vertex, Set<Vertex>> reachability(Map<Vertex, Set<Vertex>> adjList) {}

Floyd-Warshall を使用して可能であることを知っていますO(V^3)

しかし、私はスパース グラフ (および隣接リスト) を持っているので、これを行うための最速の方法は何ですか?

Floyd-Warshall アルゴリズムを使用して、2 つの頂点間の最短経路を見つけたいと考えています。マトリックスは ArrayList<ArrayList<Integer>> にあります。4x4 または 8x8 マトリックスなど、常にかなり小さいです。

私のクラスでは、距離行列が既にあります。「最短パス」マトリックスを作成しようとしています。しかし、うまくいきません。それは私のマトリックスを間違って埋めます。

誰かがこれを見て、何が悪いのか説明してくれることを本当に願っています。

私の距離行列は次のとおりです。

テスト出力は次のとおりです。

期待される：

テスト出力をコメントアウトしました。distance頂点間の距離の整数値を持つ私の行列です。私の行列でiは、y とjx です。

ここに問題のリンクがあります: http://codeforces.com/contest/295/problem/B

Greg には、n 個の頂点からなる加重有向グラフがあります。このグラフでは、異なる頂点の任意のペアの間に、両方向のエッジがあります。Greg はグラフで遊ぶのが大好きで、今では新しいゲームを発明しました。

ゲームは n ステップで構成されます。i 番目のステップで、Greg は頂点番号 xi をグラフから削除します。Greg が頂点を削除すると、この頂点に出入りするすべてのエッジも削除されます。各ステップを実行する前に、Greg は残りの頂点のすべてのペア間の最短経路の長さの合計を知りたいと考えています。最短パスは、残りの頂点を通過できます。グレッグを助けて、各ステップの前に必要な合計の値を出力してください。

入力：

最初の行には、整数 n (1 ≤ n ≤ 500) — グラフ内の頂点の数が含まれています。

次の n 行には、それぞれ n 個の整数が含まれます — グラフ隣接行列: i 行目の j 番目の数値 aij (1 ≤ aij ≤ 105、aii = 0) は、頂点 i から頂点 j に向かうエッジの重みを表します.

次の行には、n 個の異なる整数が含まれています: x1、x2、...、xn (1 ≤ xi ≤ n) — Greg が削除する頂点。

出力：

n 個の整数を出力 — i 番目の数値は、i 番目のステップの前に必要な合計に等しくなります。

INT_MAXしたがって、基本的に私のアプローチは、頂点を削除する前に Floyd-Warshall アルゴリズムを実行することでした。削除するには、行と列の両方の隣接行列のように、削除する頂点の値を設定するだけです。

基本的に、このループはmain

これは、Floyd Warshall アルゴリズムの私の実装です。

valこれは、グローバルに作成した 3D マトリックスで、arr削除する頂点が含まれています。ただし、このロジックを実行すると、正しい答えが得られるのは最初だけです。つまり、頂点が削除されていないときです。しかし、その後、間違った値が返されます。なぜだか分からない？私の論理は間違っていますか？