[플로이드워셜] 이론/ 성능/ 예제/ python 구현

- 모든 정점 사이의 최단 경로를 찾는 탐색 알고리즘임
- 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행함 (다만 매 단계마다 방문하지 않는 노드 중 최단 거리를 갖는 노드는 찾을 필요 없음)

---

- 2차원 테이블에 최단 거리 정보 저장함
예를 들어 노드가 네 개이면

0	1,2번 노드 거리	1,3번 노드 거리	1,4번 노드 거리
2,1번 노드 거리	0	2,3번 노드 거리	2,4번 노드 거리
3,1번 노드 거리	3,2번 노드 거리	0	3,4번 노드 거리
4,1번 노드 거리	4,2번 노드 거리	4,3번 노드 거리	0

---

플로이드 워셜 알고리즘 성능 분석

• 노드의 개수가 𝑁개일 때 알고리즘상으로 𝑁번의 단계를 수행한다
  • 각 단계마다 O(N²) 의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다
• 따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N³) 이다

  ---

점화식은 아래와 같음

---

 

 

예제

---

구현

 

 

초기 배열을 입력받아 최종 배열을 알고 싶은 경우

[1]

import  sys
INF = sys.maxsize

def FloydWarshall():
    dist = [[INF]*n for i in range(n)] #노드 간 최단 거리를 담는 2차원 배열
    for i in range(n):
        for j in range(n):
            dist[i][j] = a[i][j]   #초기 list로 배열 초기화
            
    for k in range(n):          #지나가는 node
        for i in range(n):      #시작 node
            for j in range(n):  #끝 node
                if dist[i][j] > dist[i][k] + dist[k][j]:    #새롭게 k를 거치는 경로가 더 짧을 때
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

n = 4
a = [[0,2,INF,4],[2,0,INF,5],[3,INF,0,INF],[INF,2,1,0]] #초기 list
dist = FloydWarshall()

for i in range(n):
    for j in range(n):
        print(dist[i][j], end = '')   #한 줄에 결과값 계속 이어가기
print()

..
..
0 2 5 4 2 0 6 5 3 5 0 7 4 2 1 0

 

 

[2]

import sys

def FloydWarshall(n, data):
	dist = [[sys.maxsize]*n for _ in range(n)]
    
    for i, j, edge in data:
    	dist[i][j] = edge
        
    for k in range(n):
    	dist[k][k] = 0
        for i in range(n):
        	for j in range(n):
            	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                
	return dist

n= 4
data = [[0,1,2],[0,3,4],[1,0,2],[1,3,5],[2,0,3],[3,1,2],[3,2,1]]
result = FloydWarshall(n,data)
print(result)