[Algorithm/Python] 플로이드 워셜 알고리즘이란?

2023. 3. 27. 00:01·🎯PS/Algorithm

들어가며

본 포스팅은 플로이드 워셜 알고리즘에 대해 소개합니다.


📌 플로이드 워셜 알고리즘

플로이드 워셜(Floyd-Warshall) 알고리즘이란, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘입니다.
기존에 소개된 다익스트라 알고리즘에서의 최단 거리 테이블에서 거리가 가장 짧은 노드를 탐색해야 했던 과정을 생략할 수 있다는 점이 차이점입니다.
 
모든 노드가 다른 노드로 가는 최단 거리의 정보를 2차원 리스트에 담아 저장합니다. 노드의 개수 N만큼 점화식에 맞게 2차원 리스트를 갱신하므로 다이나믹 프로그래밍으로 볼 수 있습니다.
 

☑️ 시간 복잡도

모든 최단 경로를 2차원 리스트에 담아 처리하므로 매번 $O(N^2)$의 시간이 소요되며, 노드의 개수 N만큼 $O(N^2)$의 연산을 통해, 해당 노드를 거치는 모든 경로를 고려합니다.
현재 노드를 거쳐 지나가는 모든 경우를 찾기 위해, N - 1개의 노드 중 2개의 쌍을 선택하고 거리를 계산합니다. 더 짧은 거리로 계산된다면, 갱신합니다. 즉, $_{N - 1}P_{2}$ 개의 쌍을 반복하여 확인하므로 $O(_{N-1}P_{2}) = O(N^2)$. 즉, 전체 시간 복잡도는 $O(N^3)$입니다.
 
$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$
이 점화식은 a와 b의 거리와, a에서 k를 거쳐 b로 이동하는 거리를 비교하여 최단 거리를 구하는 것을 의미합니다.
 
1️⃣ 그래프의 간선을 2차원 리스트로 표현합니다.
2️⃣ 현재 노드를 제외하고 $_{N - 1}P_{2}$ 개의 경우에 대해 점화식을 계산합니다.
3️⃣ 더 작은 거리로 2차원 리스트를 갱신합니다.
4️⃣ 위의 과정을 반복합니다.
 
 

1. 그래프의 간선을 2차원 리스트로 표현합니다. 간선이 없는 경우, 무한으로 표기됩니다.

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

 
2. 현재 노드인 1을 거쳐가는 경우를 모두 구하여 최단 거리를 계산합니다. ${3}P{2} = 6$ 까지의 경우에 대한 점화식은 다음과 같습니다.

$D_{23} = min(D_{23}, D_{21} + D_{13})$
$D_{24} = min(D_{24}, D_{21} + D_{14})$
$D_{32} = min(D_{32}, D_{31} + D_{12})$
$D_{34} = min(D_{34}, D_{31} + D_{14})$
$D_{42} = min(D_{42}, D_{41} + D_{12})$
$D_{43} = min(D_{43}, D_{41} + D_{13})$
 

출발 / 도착 1 2 3 4
1 0 4 무한 6
2 3 0 7 무한, 9(갱신)
3 5 무한, 9(갱신) 0 4
4 무한 무한 2 0

 
3. 현재 노드인 2를 거쳐가는 경우를 모두 구하여 최단 거리를 계산합니다.

출발 / 도착 1 2 3 4
1 0 4 무한, 11(갱신) 6
2 3 0 7 9
3 5 9 0 4
4 무한 무한 2 0

 
4. 현재 노드인 3을 거쳐가는 경우를 모두 구하여 최단 거리를 계산합니다.

출발 / 도착 1 2 3 4
1 0 4 11 6
2 3 0 7 9
3 5 9 0 4
4 무한, 7(갱신) 무한, 11(갱신) 2 0

 
5. 현재 노드인 4를 거쳐가는 경우를 모두 구하여 최단 거리를 계산합니다.

출발 / 도착 1 2 3 4
1 0 4 11, 8(갱신) 6
2 3 0 7 9
3 5 9 0 4
4 7 11 2 0

 
 

✅ [ CODE ]

'''
< 플로이드 워셜 알고리즘 >
'''
import sys

input = sys.stdin.readline
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF] * (n + 1) for _ in range(n + 1)]

for x in range(1, n + 1):
    for y in range(1, n + 1):
        if x == y:
            graph[x][y] = 0
            break 

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c

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 a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print("INFINITY")
        else:
            print(graph[a][b], end = " ")
    print()

포스팅에 문제 및 오류가 있는 경우, 댓글로 남겨주시면 감사하겠습니다.

 

출처 ) 이것이 코딩 테스트다 with Python

반응형
저작자표시 (새창열림)
'🎯PS/Algorithm' 카테고리의 다른 글
  • [Algorithm/Python] 크루스칼 알고리즘이란? || 최소 신장 트리
  • [Algorithm/Python] 서로소 집합(Disjoint Sets) 알고리즘이란?
  • [Algorithm/Python] 다익스트라 최단 경로 알고리즘이란? || dijkstra
  • [Algorithm/Python] 이진 탐색(Binary Search)란?
dmaolon
dmaolon
프로그래밍을 공부한 내용을 기록하는 공간입니다.
  • dmaolon
    기록 남기기
    dmaolon
  • 전체
    오늘
    어제
    • ALL (260)
      • ➰ Series (5)
      • 🎯PS (168)
        • Algorithm (15)
      • ☕ Java (11)
      • 🍀 Spring Boot (29)
      • 💬 Database (9)
      • 🐣 Computer Science (14)
      • 👍 Daily (4)
      • 🎁ReactJS (4)
  • 인기 글

  • 최근 댓글

  • 최근 글

  • 태그

    알고리즘
    파이썬
    Spring
    BFS
    백준
    프로그래밍
    프로그래머스
    dfs
    코딩
    자바
  • hELLO· Designed By정상우.v4.10.1
dmaolon
[Algorithm/Python] 플로이드 워셜 알고리즘이란?
상단으로

티스토리툴바