技術共有

フロイドのアルゴリズム - AcWing 343. 並べ替え

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

目次

フロイドアルゴリズム

意味

使用法

予防

問題解決のアイデア

基本的な手順

AcWing 343. 仕分け

質問の説明

コードを実行する

コードのアイデア

アイデアを改善する

フロイドアルゴリズム

意味

フロイド アルゴリズム (フロイド ウォーシャル アルゴリズムの正式名) は、グラフ内の頂点のすべてのペア間の最短経路問題を解くために使用される動的計画法アルゴリズムです。これは重み付き有向グラフに適しており、負の重みエッジを処理でき (ただし、負の重みサイクルを含むグラフは処理できません)、グラフ内に負の重みサイクルがあるかどうかを検出できます。

使用法

  1. すべての頂点ペア間の最短パスを計算します。: 社会ネットワーク分析、交通ネットワーク計画、通信ネットワーク設計などの分野で、任意の 2 点間の最短距離を計算する必要がある場合には、Floyd アルゴリズムが適しています。
  2. マイナスの体重サイクルを検出: 一部のアプリケーション シナリオでは、グラフに負の重みサイクルがないことを確認する必要があります。これは、システム内の何らかの異常またはエラー状態を示している可能性があるためです。

予防

  • メモリ消費量 : フロイドのアルゴリズムの空間計算量は O(n^2) です。ここで、n はグラフ内の頂点の数です。大規模なグラフの場合、これが問題になる可能性があります。
  • 時間の複雑さ: フロイドのアルゴリズムの時間計算量は O(n^3) であり、頂点の数が多い場合、アルゴリズムは非常に遅くなる可能性があります。
  • 負の重みループ : グラフに負の重みサイクルがある場合、ノードから開始してこのサイクルを通じてパスの長さを無限に短縮できるため、フロイドのアルゴリズムは無限ループに陥ります。実際のアプリケーションでは、このような状況を最初に検出して処理する必要があります。
  • アルゴリズムは負の体重サイクルを検出できます。アルゴリズムの実行中に、頂点から頂点自体への最短経路が 0 未満であることが判明した場合、つまり D[i][i] < 0 である場合、グラフ内に少なくとも 1 つの負の重みサイクルが存在します。現時点では、アルゴリズムは正しい最短パスの結果を与えることができません。
  • 非常に大きなグラフの場合、アルゴリズムの時間と空間の複雑さがボトルネックになる可能性があり、より効率的なアルゴリズムを検討するか、より専門的なデータ構造と最適化手法を使用する必要がある場合があります。

問題解決のアイデア

フロイドのアルゴリズムの核となる考え方は動的計画法であり、その基本的な手順は次のとおりです。

  1. 初期化: 距離行列 D をグラフの隣接行列に設定します。つまり、(i, j) が接続されていない場合は、D[i][j] = Weight(i, j) になります。 D[i][ j] = ∞; D[i][i] = 0。
  2. 動的プログラミング: k = 1 ～ n の場合、D[i][j] = min(D[i][j], D[i][k] + D[k][j]) となるように D を更新します。 i から j までの距離が中間ノード k を介して短縮できるかどうかを確認します。
  3. 結果: 最終的な D 行列には、頂点のすべてのペア間の最短パス長が含まれます。特定の D[i][j] < 0 および i != j があり、更新プロセス中に D[i][i] < 0 が発生した場合、グラフ内に負の重みサイクルがあることを意味します。

フロイドのアルゴリズムの実装では通常、三重ループが使用され、外側のループはすべての中間頂点 k を走査し、内側の 2 つのループはすべての頂点ペア (i, j) を走査して、より短いパスがあるかどうかを確認します。

基本的な手順

n 個の頂点を含む重み付きグラフ G があると仮定すると、2 次元配列を使用できます。dist[][]頂点の各ペア間の最短パス長を保存します。当初は、dist[i][j]i と j の間に直接接続されたエッジがない場合、 はグラフ内の直接接続されたエッジの重みに設定されます。dist[i][j]無限大に設定します (到達不能を示します)。

  1. 初期化 : n×n 行列 D を作成します。ここで、D[i][j] はグラフ内の i から j までの直接エッジの重みに初期化されます。または、i と j の間に直接エッジがない場合は無限大に設定されます。対角要素 D[i][i] = 0。

  2. 動的プログラミング : 各頂点 k について (中間頂点として)、頂点 i と j の各ペア間の最短パスを更新します。k を中間点として、より短いパスを取得することが可能です。更新式は次のとおりです: D[i][j] = min(D[i][j], D[i][k] + D[k][j])。これは、k を中間頂点として i から j までの経路が短くなった場合、D[i][j] を更新することを意味します。

  3. 結果出力: n ラウンドの反復の後、行列 D の各要素 D[i][j] は、i から j への最短経路長になります。

AcWing 343. 仕分け

質問の説明

343. 並べ替え - AcWing クエスチョンバンク

コードを実行する

  1. #include <algorithm>
  2. #include <bits/stdc++.h>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. #define PII pair<int, int>
  7. #define fi first
  8. #define se second
  9. #define endl 'n'
  10. map<int, int> mp;
  11.  
  12. const int N = 210, mod = 1e9 + 7;
  13. int T, n, m, k;
  14. int a[N], dist[N][N];
  15. PII ans[N];
  16.  
  17. void floyd(int x) // 以 x 为中转点，更新其他点。
  18. {
  19.     for (int i = 1; i <= n; i++)
  20.         for (int j = 1; j <= n; j++)
  21.             dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
  22. }
  23.  
  24. bool pd() // 判断是否所有点都已确定
  25. {
  26.     for (int i = 1; i <= n; i++) {
  27.         int cnt = 0;
  28.         for (int j = 1; j <= n; j++)
  29.             if (dist[i][j] != 1e9)
  30.                 cnt++; // 当前点能到达的点数
  31.         ans[i] = {cnt, i};
  32.         for (int j = 1; j <= n; j++)
  33.             if (i != j && dist[j][i] != 1e9)
  34.                 cnt++; // 能到达当前点的点数
  35.         if (cnt != n)
  36.             return 0;
  37.     }
  38.     sort(ans + 1, ans + n + 1);
  39.     return 1;
  40. }
  41.  
  42. int main() {
  43.     while (cin >> n >> m && n) {
  44.         for (int i = 1; i <= n; i++)
  45.             for (int j = 1; j <= n; j++)
  46.                 if (i != j)
  47.                     dist[i][j] = 1e9;
  48.  
  49.         int flag = 0;
  50.         for (int i = 1; i <= m; i++) {
  51.             char a, t, b;
  52.             cin >> a >> t >> b;
  53.             int x = a - 'A' + 1, y = b - 'A' + 1; // 现在要加一条从 y 到 x 的边
  54.  
  55.             if (!flag && dist[x][y] != 1e9) // 发现已经从x能到y，出现矛盾
  56.             {
  57.                 printf("Inconsistency found after %d relations.n", i);
  58.                 flag = 1;
  59.             }
  60.  
  61.             dist[y][x] = 1;
  62.             floyd(x), floyd(y); // 分别以 x 和 y 为中转点更新其他点
  63.             if (!flag && pd()) { // 发现所有点都已确定
  64.                 printf("Sorted sequence determined after %d relations: ", i);
  65.                 for (int i = 1; i <= n; i++)
  66.                     cout << char(ans[i].se + 'A' - 1);
  67.                 printf(".n");
  68.                 flag = 1;
  69.             }
  70.         }
  71.         if (!flag)
  72.             printf("Sorted sequence cannot be determined.n"); // 无法确定
  73.     }
  74.  
  75.     return 0;
  76. }

コードのアイデア

  1. 初期化： 使うdist2 次元配列は無限大に初期化されます。これは、デフォルトでは不等式間に明確な順序関係がないことを意味します。
  2. 入力の読み取り: 標準入力から関係を「B &gt; A」形式で読み取り、B が A よりも優れていることを示します。
  3. 関係処理:
    • 新しい関係が読み込まれると、矛盾があるかどうか (つまり、以前に決定された関係が新しい関係と競合するか) がチェックされます。
    • 更新するdistマトリックスは、フロイドのアルゴリズムを使用してすべての不等式間の最短経路を更新しますが、ここでは実際に「優先順位」または「順序付け」関係を更新しています。
  4. 仕分けの確実性をチェックする:
    • すべての不等式が関連していること、つまり、すべての点が他のすべての点に到達でき、経路の長さが無限ではないことを確認してください。
    • リレーションシップを読み込む過程でソートが見つかった場合、またはすべてのリレーションシップを読み取ってもソートが決定できない場合は、対応する情報が出力されます。

アイデアを改善する

  • 効率向上 : 現在の floyd 呼び出しは、新しい関係が追加されるたびにすぐに行われますが、これは必要ない場合があります。不必要な計算を減らすために、すべての関係が読み取られるまで待ってから、フロイドのアルゴリズムを再度実行することができます。
  • ロジックを単純化する : 現在のコードは、矛盾の検出とソート完了のロジックの決定においてより複雑です。これらの条件をチェックするために、より直観的なデータ構造やアルゴリズム手順を使用するなど、ロジックの簡素化を試みることができます。
  • コードの明瞭さ: コメントとコード構造が明確になり、コードの理解と保守が容易になります。

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

私の連絡先情報

郵便