[TIL] 플로이드 와샬 Floyd Warshall

플로이드 와샬 Floyd Warshall 

모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
거쳐가는 정점을 기준으로 최단 거리를 구한다 

 

플로이드 와샬 특징 

1. 시작 정점과 도착 정점의 구분 없이 모든 경로에 대한 최단 경로를 구하는 데 사용된다

2. 동적 계획법을 사용하여, 경로가 점차적으로 개선되면서 최단 경로를 찾는다

3. 음수 가중치를 갖는 그래프에서도 동작하지만, 음수 사이클이 있으면 알고리즘이 제대로 동작하지 않는다

  (음수 사이클 - 음수 가중치를 갖는 경로로 인해 무한히 작은 경로가 생기는 경우)

4. 시간 복잡도 가 O(N^3) 으로, 정점의 수가 적을 때는 효율적이지만 정점 수가 많을 수록 비효율적일 수 있다 

5. 인접 행렬로 표현하여 사용되며, 행렬의 각 값은 두 정점 사이의 최단 경로 가중치를 나타낸다

도로망 분석, 중계 노드 찾기 등에서 사용할 수 있다

플로이드 와샬 동작 과정 

0. 초기값 

출발 \ 도착	1번	2번	3번	4번
1번	0	4	무한	6
2번	3	0	7	무한
3번	5	무한	0	4
4번	무한	무한	2	0

 

 

1. 1번 노드를 거쳐가는 경우를 고려하여 테이블을 갱신한다 

출발 \ 도착	1번	2번	3번	4번
1번	0	4	무한	6
2번	3	0	7	9
3번	5	9	0	4
4번	무한	무한	2	0

 

2. 2번 노드를 거쳐가는 경우를 고려하여 테이블을 갱신한다

출발 \ 도착	1번	2번	3번	4번
1번	0	4	11	6
2번	3	0	7	9
3번	5	9	0	4
4번	무한	무한	2	0

 

3. 3번, 4번 노드를 거쳐가는 경우를 고려하여 테이블을 갱신한다

출발 \ 도착	1번	2번	3번	4번
1번	0	4	11	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

 

출발 \ 도착	1번	2번	3번	4번
1번	0	4	8	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

 

 

노드의 개수가 N개일 때 N번의 단계를 수행하며 단계마다 O(N^2) 의 연산을 통해

'현재 노드를 거쳐가는 모든 경로'를 고려하기 때문에 시간 복잡도는 O(N^3) 이다 

k 거쳐가는 노드, i 출발 노드, j 도착 노드로 3번 for 문을 돌린다 

 

플로이드 와샬 코드 구현

# 무한대를 나타내기 위한 값 설정 
INF = float('inf')

def floyd_warshall(n, graph):
    # 각 노드에서 다른 노드로 가는 최소 거리를 기록할 배열 
    # 초기값은 무한대로 설정  
    dist = [[INF]*n for _ in range(n)]

    # 자기 자신으로 가는 거리는 0 으로 설정 
    for i in range(n):
        dist[i][i] = 0

    # 주어진 그래프의 거리 정보를 거리 dist 배열에 초기화 
    for u in range(n):
        for v in range(n):
            dist[u][v] = graph[u][v]

    # 플로이드 와샬 알고리즘 적용
    # k 는 거쳐가는 노드, i 는 출발 노드, j 는 도착 노드 
    for k in range(n):
        for j in range(n):
            for i in range(n):
                # 기존 dist[i][j] 의 값과 dist[i][k] + dist[k][j] 의 값을 비교 
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

    return dist

if __name__ == '__main__':

 
    n = 4 # 노드의 개수 
    # 인접 행렬
	graph = [
        [0, 4, INF, 6],
        [3, 0, 7, INF],
        [5, INF, 0, 4],
        [INF, INF, 2, 0]
    ]

    # 플로이드 와샬 알고리즘 수행 
    result = floyd_washall(n, graph)

    # 결과를 2차원 배열 형태로 출력 
    for row in result:
        print(row)
        
	# 결과 출력
	# [0, 4, 8, 6]
	# [3, 0, 7, 9]
	# [5, 9, 0, 4]
	# [7, 11, 2, 0]