Flood-Whallアルゴリズム

10306 ワード
アルゴリズム#アルゴリズム# テキストリンク
Flood-Whallアルゴリズム
💡すべてのノードから他のすべてのノードへの最短パスを計算
  • マルチ出口と同様に、ステップノードに基づいてアルゴリズムBUTチェック
    • を実行する必要はない.
    最短距離情報を
  • の2次元テーブルに記憶する、DPタイプ
    • を点火式で更新する.
  • 時間複雑度O(V^3)->ノードが500個を超えると
    • タイムアウトする可能性があります.
    n/a原理
    各ステップが特定のノードKを通過することを確認する.
    ->a~bの最短距離はa~k~bの最短距離より短い
    D(a, b) = min(D(a,b), D(a,k) + D(k, b))
    アルゴリズム#アルゴリズム#
    for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    大きい値の初期化
  • 2 2 2 Dリスト
  • 自己から自己への費用を0
    • に初期化する.
  • の各幹線の情報を入力し、値に初期化します.
    ->g[出発][到着]=料金
    • を更新し、「通過」ノードと元のノードのコストを比較
  • すべてのノードからすべてのノードへの最低コスト





    • コード#コード#
    # 11404 플로이드 - 골드4 김수민
N = int(input())
M = int(input())
cost = [[1e9] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    start, end, dis = map(int, input().split())
    cost[start][end] = min(dis, cost[start][end])

# 플로이드-와샬 알고리즘
for k in range(1, N + 1):
    cost[k][k] = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

# 출력
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if cost[i][j] == 1e9:
            cost[i][j] = 0
        print(cost[i][j], end=' ')
    print()
    [注意]
    https://freedeveloper.tistory.com/385
    小数点を検索(レベル2)
    [コードテストC+]宝石泥棒