[알고리즘] 플로이드 워셜 with Python

💡 최단 경로 알고리즘

  가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길찾기'문제라고도 불린다. 학부 수준에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 이렇게 3가지이다. 이 중 플로이드 워셜 알고리즘을 이번 포스팅에서 다뤄보려고 한다.

💡 플로이드 워셜 알고리즘

  다익스트라 알고리즘은 '한 지점'에서 다른 모든 노드까지의 최단경로를 계산하는 알고리즘이였다. 플로이드 워셜 알고리즘은 '모든 노드'에서 다른 모든 노드까지의 최단경로를 모두 계산하는 알고리즘이다. 

 플로이드 워셜 알고리즘은 노드의 개수가 N이라고 할때 N번만큼의 단계를 반복하며 '점화식'에 맞게 2차원 리스트를 갱신하기 때문에 다이나믹 프로그래밍으로 볼 수 있다. 구현 난이도가 다익스트라 알고리즘보다 쉽지만, 시간복잡도가 O(N^3)이기 때문에 노드와 간선 수가 작을 때만 사용해야한다. (노드의 갯수가 약 500개 이하일때만 고려해야한다.)

💡 플로이드 워셜 알고리즘 동작 과정

  각 단계에서는 해당 노드를 거쳐가는 경우를 고려한다. 예를 들어 k번 노드에 대해서 확인할 때는 k번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하면된다. 이를 점화식으로 표현하면 다음과 같다.

D(a,b) = min(D(a,b), D(a,k)+D(k,b))

점화식을 의미하는 내용을 풀어서 설명하면 (a에서 b로 가는 최단거리, a에서 k를 거쳐서 b로 가는 거리)를 비교하여 더 작은 값으로 갱신하겠다는 것이다. 즉, k를 거쳐가는 것이 빠르다면 최단거리 테이블을 갱신하겠다는 의미이다.

 

[step0]

주어진 연결정보를 이용해서 테이블을 초기화한다.

인접한 노드라면 그 비용을 값으로 넣고 인접한 노드가 아니라면 무한이라는 값을 넣는다. 

[step1]

1번 노드를 거쳐 가는 경우를 고려한다. 

정확히 3*2=6가지 경우에 대해서만 고려하면된다. 

6가지 경우에 대해서 점화식을 계산한다. 

D(2,3) = min(D(2,3), D(2,1)+D(1,3)) = min(7, 3+INF)

D(2,4) = min(D(2,4), D(2,1)+D(1,4)) = min(INF, 3+6)

D(3,2) = min(D(3,2), D(3,1)+D(1,2)) = min(INF, 5+4)

D(3,4) = min(D(3,4), D(3,1)+D(1,4)) = min(4, 5+6)

D(4,2) = min(D(4,2), D(4,1)+D(1,2)) = min(INF, INF+4)

D(4,3) = min(D(4,3), D(4,1)+D(1,3)) = min(2, INF+INF)

[step2]

2번 노드를 거쳐 가는 경우를 고려한다.

마찬가지로 3*2=6가지 경우에 대해서 점화식을 계산한다. 

마찬가지 방법으로 노드3, 노드4에 대해서도 반복한다. 최종결과는 다음과 같다.

이 2차원 리스트가 표현하는 바는 D(2,3)=7, 2번 노드에서 3번 노드로 가는 최단거리가 7임을 의미한다.

이렇게 '모든 노드'에서 다른 모든 노드까지의 최단경로를 모두 계산하여 2차원리스트로 저장하였다.

 

모든 노드에서 다른 모든 노드까지의 최단경로

💡 플로이드 워셜 알고리즘 구현

INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())

# 최단경로 리스트
# 노드번호가 1번부터 시작하여(n+1)로 설정
graph = [[INF]*(n+1) for _ in range(n+1)]

# 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
  for b in range(1,n+1):
    if a==b:
      graph[a][b] = 0

# 노드의 연결 정보를 입력받아 그 값으로 초기화
for _ in range(m):
  # A에서 B로 가는 비용은 C
  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("X", end =" ")
    else: # 도달할 수 있는 경우
      print(graph[a][b], end=" ")
  print() # 줄바꿈

💡 플로이드 워셜 알고리즘 예시

Q1. 미래도시

  미래도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어있다. 방문 판매원 A는 현재 1번 회사에 위치해있으면 X번회사에 방문해 물건을 판매하고자 한다. 미래도시에서 특정회사에 도착하기 위한 방법은 회사끼리 연결된 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 미래 도시에서의 도로는 마하의 속도로 사람을 이동시켜주기 때문에 특정회사와 다른 회사가 도로로 연결되어있다면 정확히 1만큼의 시간으로 이동할 수 있다.

  또한 오늘 방문판매원은 기대하던 소개팅에도 참석하고자한다. 소개팅 상대는 K번 회사에 존재한다. 방문 판매원 A는 X번회사에 가서 물건을 판매하기 전에 먼저 소개팅 상대의 회사에 찾아가서 함께 커피를 마실 예정이다. 따라서 방문 판매원 A는 1번회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표다. 이때 방문판매원 A는 가능한 한 빨리 이동하고 싶다.방문 판매원이 회사 사이를 이동하게 되는 최소시간을 계산하느 프로그램을 작성하시오, 이때 소개팅의 상대방과 커피를 마시는 시간은 고려하지 않는다고 가정한다.

 

*입력조건

- 첫째줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다.(1<=N,M<=100)

- 두번째줄부터 M+1번째 줄에는 연결된 두회사의 번호가 공백으로 구분되어 주어진다.

- M+2번째줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다.(1<=K<=100)

*출력조건

- 첫번째 줄에 방문 판매원 A가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다.

- 만약 X에 도달할 수 없다면 -1을 출력한다.

 

입력 예시	출력 예시
5 7 1 2 1 3 1 4 2 4 3 4 3 5 4 5 4 5	3
4 2 1 3 2 4 3 4	-1

 

[문제 아이디어]

전체 회사의 개수와 경로의 경수가 100개 이하로 크지 않다. 1번에서 K로 이동하는 경우와 K에서 X로 이동하는 두가지의 경우가 있으므로 이는 플로이드 워셜 알고리즘을 사용했을때 효과적으로 해결할 수 있다.

 

[코드]

INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())

# 최단경로 리스트
# 노드번호가 1번부터 시작하여(n+1)로 설정
graph = [[INF]*(n+1) for _ in range(n+1)]

# 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
  for b in range(1,n+1):
    if a==b:
      graph[a][b] = 0

# 노드의 연결 정보
for _ in range(m):
  # A에서 B로 가는 비용은 1로 동일. 양방향이다.
  a,b = map(int, input().split())
  graph[a][b] = 1
  graph[b][a] = 1

# 거쳐갈 노드 k와 최종 목적지 x
x, k = map(int, input().split())

# 점화식에 따라 플로이드 워셜 알고리즘 수행
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])

# 수행된 결과를 출력
result = graph[1][k]+graph[k][x]

#도달 불가능
if result >= INF :
  print("-1")
else: # 도달할 수 있는 경우
  print(result, end=" ")