플로이드와샬 / 플로이드 - 와샬

■ 플로이드와샬

1) 정의 :

3중 for문을 통해 

모든 정점사이의 최단 경로를 찾는 탐색 알고리즘

> (다대다 정점간 최단경로 모두 찾아야 할 때)

> 최대 O(N^3) 시간복잡도

> 간선모두 탐색하며 dynamic 하게 업데이트 하므로

   인접행렬로 구현

 

 

 

■ 과정

1) 한 노드에서 다른 노드로 갈 수 있으면 최소 비용 / 간선이 없으면 INF로 초기 배열을 설정

2) 3중 for문을 통해 "거쳐가는 정점"을 기준으로, 다른 경로를 선택할 때 비용이 줄면, 값을 갱신 (다이나믹 프로그래밍)

3) 1~2 반복으로 모든 정점 사이의 최단경로를 탐색

---

1) 초기 배열 세팅

INF = float('inf')
adj = [
    [0, 5, INF, 8],
    [7, 0, 9, INF],
    [2, INF, 0, 4],
    [INF, INF, 3, 0]
]

2) 거쳐가는 정점을 1차 for문의 값으로 설정하고 나머지 계산

3) i 에서 k를 거쳐 j로 가는 것과 i 에서 바로 j로 가는것
   > adj[i][k] + adj[k][j] 와 adj[i][j] 를 비교

 

 

■ 구현

def floyd_warshall(N, graph):
    # 거쳐가는 노드 K 기준
    for k in range(N):
        # 출발 정점 i
        for i in range(N):
            # 도착 정점 j
            for j in range(N):
                # i에서 k를 거쳐 j 까지 가는 것과 i에서 j까지 바로가는 것중 
                # 계산 값이 더 작은 것으로 원 그래프 값을 dynamic하게 갱신
                graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
    
    return graph

 

 

■ 예시

# 가중치 인접행렬  # 바로 연결이 안돼있는 경우 INF(무한대)
from pprint import pprint
N = 4
INF = float('inf')
adj = [
    [0, 5, INF, 8],
    [7, 0, 9, INF],
    [2, INF, 0, 4],
    [INF, INF, 3, 0]
]

print('가중치 인접 행렬')
for row in adj:
    print(row)
print()

def floyd_warshall(N, graph):
    # 거쳐가는 정점 k를  기준으로
    for k in range(N):
        # 출발 정점 i 에서
        for i in range(N):
            # 도착 정점 j 까지
            for j in range(N):
                # i에서 k를 거쳐 j 까지 가는 것과 i에서 j까지 바로가는 것중 값이 더 작은 것으로 갱신
                print(f'graph before :')
                pprint(graph,  width=40, indent=4)
                print(f'k 거쳐가는 정점 : {k}')
                print(f'from 정점 i : {i}, to 정점 j : {j}')
                print(f'graph[i][k] + graph[k][j] : {graph[i][k] + graph[k][j]}')
                print(f'graph[i][j] : {graph[i][j]}')
                graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
                print(f'graph after :')
                pprint(graph,  width=40, indent=4)
                print(f'\n'*2)
    
    return graph


adj = floyd_warshall(N, adj)

print('결과')
for row in adj:
    print(row)
print()


>>>
가중치 인접 행렬
[0, 5, inf, 8]
[7, 0, 9, inf]
[2, inf, 0, 4]
[inf, inf, 3, 0]




graph before :
[   [0, 5, inf, 8],
    [7, 0, 9, inf],
    [2, inf, 0, 4],
    [inf, inf, 3, 0]]
k 거쳐가는 정점 : 0
from 정점 i : 0, to 정점 j : 0
graph[i][k] + graph[k][j] : 0
graph[i][j] : 0
graph after :
[   [0, 5, inf, 8],
    [7, 0, 9, inf],
    [2, inf, 0, 4],
    [inf, inf, 3, 0]]



... (중략) ...

graph before :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [inf, inf, 3, 0]]
k 거쳐가는 정점 : 2
from 정점 i : 3, to 정점 j : 0
graph[i][k] + graph[k][j] : 5
graph[i][j] : inf
graph after :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, inf, 3, 0]]



graph before :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, inf, 3, 0]]
k 거쳐가는 정점 : 2
from 정점 i : 3, to 정점 j : 1
graph[i][k] + graph[k][j] : 10
graph[i][j] : inf
graph after :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, 10, 3, 0]]



graph before :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, 10, 3, 0]]
k 거쳐가는 정점 : 2
from 정점 i : 3, to 정점 j : 2
graph[i][k] + graph[k][j] : 3
graph[i][j] : 3
graph after :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, 10, 3, 0]]



graph before :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, 10, 3, 0]]
k 거쳐가는 정점 : 2
from 정점 i : 3, to 정점 j : 3
graph[i][k] + graph[k][j] : 7
graph[i][j] : 0
graph after :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, 10, 3, 0]]



graph before :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, 10, 3, 0]]
k 거쳐가는 정점 : 3
from 정점 i : 0, to 정점 j : 0
graph[i][k] + graph[k][j] : 13
graph[i][j] : 0
graph after :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, 10, 3, 0]]



graph before :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, 10, 3, 0]]
k 거쳐가는 정점 : 3
from 정점 i : 0, to 정점 j : 1
graph[i][k] + graph[k][j] : 18
graph[i][j] : 5
graph after :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, 10, 3, 0]]



graph before :
[   [0, 5, 14, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, 10, 3, 0]]
k 거쳐가는 정점 : 3
from 정점 i : 0, to 정점 j : 2
graph[i][k] + graph[k][j] : 11
graph[i][j] : 14
graph after :
[   [0, 5, 11, 8],
    [7, 0, 9, 13],
    [2, 7, 0, 4],
    [5, 10, 3, 0]]

... (중략) ...



결과
[0, 5, 11, 8]
[7, 0, 9, 13]
[2, 7, 0, 4]
[5, 10, 3, 0]

---

참조 :
deok2kim.tistory.com/174

플로이드 와샬(Floyd Warshall)

seoyoung2.github.io/algorithm/2020/07/22/Floyd-Warshall.html

[python] 플로이드와샬 알고리즘, 플로이드(Baekjoon, 11404) - LunaLunaఇ

it-garden.tistory.com/247

플로이드-워셜(Floyd-Warshall) 알고리즘 이론과 파이썬 구현