💡 フロイド・ワッシャーアルゴリズムとは?

以前に学習したマルチアウトプットアルゴリズムとベルマン・フォードアルゴリズムが特定のノードの最短距離を求めることができるアルゴリズムである場合、floyd−wassalアルゴリズムはすべてのノード間の最短距離を求めることができる.そう言えばもっと難しいアルゴリズムかもしれませんが、前のアルゴリズムに比べて実現の難しさは低いです.

🤔 どのように実現しますか?

コア原理は,特定のノードを通過したときの距離値と現在格納されている最短距離値を比較することによって値を更新する.これを点火式として表します.以下に示します.

Dは、元の記憶されているaノードからbノードまでの距離を示す下書きである.点画法を用いて部分的に問題を解決し,最小値をグラフィックの配列に書き込むことができるため,floyd−wassalアルゴリズムは動的プログラミングに属する.ノードの個数がKの場合、すべてのノードをKのノードの周りで比較する必要があるので、三重複文を使用します.従って,時間的複雑度は多翼点アルゴリズムよりも大きいので,条件をよく見て用いなければならない.通常、ノードが500個以下であり、問題ですべてのノード間の最短パスを求める必要がある場合に使用される.
アルゴリズムの特徴時間の複雑さは多益straの特定のノードの他のノードの最短距離までであり,重み付け値は正の値(‖E‖+‖V‖log‖V‖)Oでなければならない.負の値を持つ重み付けO(‖V‖E‖)O(|V|E|)O(‖V‖E‖)フロイドとすべてのノードとの最短距離をカバーすることができ、負の値を含んでもO(V 3‖V^3‖)O(V^3|O)を使用することができる.

💻 実現しましょう!

これはBaek JunでFloyd−Wassalアルゴリズムを用いた代表的な問題である.11404号.

import sys
input = sys.stdin.readline

INF = 1e9

n = int(input())
m = int(input())

# 그래프 배열 만들고 자기 자신은 0으로 설정
graph = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0

# 시작 도시, 도착 도시, 버스 한 번 타는데 필요한 비용을 입력받아 graph에 저장
# 이 때 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있으므로 같은 노선일 경우 최솟값을 저장
for i in range(m):
    a, b, c = map(int, input().split())
    if graph[a][b] > c:
        graph[a][b] = c

# 플로이드-와셜 알고리즘
# 특정 노드 k를 거쳐가는 경우를 생각해서 k를 안거치는 경우의 값과 k를 거치는 경우의 값을 비교해서 갱신
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] >= INF:
            print(0, end=' ')
        else:
            print(graph[i][j], end=' ')
    print()