1. 최단경로 알고리즘
특정노드에서 다른 노드로 향하는 가장 적은 비용, 최단 거리를 도출하는 알고리즘을 의미한다.
최단경로를 도출하는 알고리즘을 활용할 수 있는 형태는 크게 3가지로 나뉘어져있다.
- 한 지점에서 다른 한 지점으로 향하는 최단경로(최소비용)
- 한 지점에서 모든 노드 지점까지 향하는 최단경로(최소비용)
- 모든 지점에서 다른 모든 노드 지점까지 향하는 최단경로(최소비용)
2. 플로이드 와샬 알고리즘
다익스트라 알고리즘과 마찬가지로 최단 경로를 도출하는 알고리즘 중 하나이다.
다만 다익스트라가 최초 출발노드를 시작으로 다른 모든 노드로 향하는 경로를 도출하는 알고리즘이라면, 플로이드 와샬 알고리즘은 모든 노드를 출발하여 모든 노드로 향하는 경로를 도출하는 알고리즘이다.
- 다익스트라는 result가 1행(특정 노드에서 다른 모든 노드로 향하는 최단 경로)이라면, 플로이드 와샬은 result가 n행(node개수)이다.
- 매 단계마다 방문하지 않은 노드를 확인(혹은 이에 준하는 확인)하는 과정을 진행하지 않아도 된다.
- 모든 노드에서 모든 노드로 가는 경로가 담겨지므로, 최종 경로는 2차원 테이블에 담겨진다.
- 점화식에 따라 최단거리를 갱신하는 DP유형에 속한다.
※ a에서 b로 향하는 최단 경로의 점화식은, Dab = min(Dab,Dak+Dkb)(단, k는 거쳐가는 노드).
※ 다익스트라 자체도 따지고 보면, 그리디 알고리즘이기도 하고 거쳐가는 노드에 대해 매 단계마다 최소값으로 결정하기 때문에 본질적으로 동일한 점화식을 따른다고 보면 된다. - 다익스트라와는 달리 최초 최단경로 테이블을 인접노드를 기준으로 최초 graph 상태 그대로 반영하여 구현한다.
2-1. 플로이드 와샬 알고리즘 구현 시 단계별 과정
최단 경로 테이블을 무한으로 구성하지 않고, 각 노드의 관계를 기준으로 최초 graph 상태를 반영한다.
- step 1
1번 노드를 거쳐가는 경우에 대한 최단 경로 테이블을 작성한다.
이때 출발점이 1이거나, 종료지점이 1인 경우는 제외하고 1을 거쳐가서 다른 노드로 향하는 경우에만 테이블을 작성한다.
Dab = min(Dab, Dak+Dkb)
- step 2
이 과정을 다른 모든 노드들에 대해 진행한다.
갱신이 완료된 최단경로 테이블은 행 노드에서 열 노드로 향할때, direct로 향하거나 특정 노드를 거쳐거나 상관없이 최단 경로를 반영하고 있다.
2-2. 알고리즘 구현
import sys
INF = int(1e9)
#노드, 간선 개수
n, m = map(int, sys.stdin.readline().split())
#graph 초기화, 최초 상태는 모두 INF
#노드1부터 간주하기 위해 n+1씩 반복
graph = [[INF] * (n+1) for _ in range(n+1)] #만드는 크기 자체는 n+1행 * n+1열
#자기자신에서 자기자신으로 가는 비용은 0으로 초기화
#n행 m열의 개념이 아닌, 노드 개수 n개와 간선 개수 m개에 유의한다.
for i in range(1, n+1):
for j in range(1, n+1):
if i == j:
graph[i][j] = 0
#각 간선개수만큼 순회하여 간선 정보를 입력
for _ in range(m):
#a에서 b로가는 비용은 c
a, b, c = map(int, sys.stdin.readline().split())
graph[a][b] = c
#플로이드 워셜 알고리즘 적용 - 3중 반복
for i in range(1, n+1): #노드 개수만큼(n개), 가장 기준이 되는 반복인자(거쳐가는 기준 노드)
for j in range(1, n+1): #노드 개수만큼(n개)
for k in range(1, n+1):
graph[j][k] = min(graph[j][k], graph[j][i]+graph[i][k])
#수행결과 출력
for i in range(1, n+1):
for j in range(1, n+1):
if graph[i][j] == INF #도달할 수 없는 경우
print("INFINITY")
else:
print(graph[i][j], end=" ")
#그래프를 출력하되 같은 행에 대해서는 줄바꿈이 일어나지 않도록(공백표시)
print() #같은 행 반복 후 줄바꿈2-3. 시간복잡도
N개의 노드에 대하여 N행*N열번 반복연산을 수행한다.
- 시간복잡도는 O(N^3)이다.
- 노드 개수가 조금이라도 많아진다면 시간복잡도가 기하급수적으로 늘어나므로, 다익스트라 알고리즘으로 구성하는 방안을 고민한다.
- 다만 무조건적으로 플로이드 와샬이 안좋다는 의미는 아니므로, 노드개수 및 문제 상황에 따라 알맞게 알고리즘 구현 방식을 적용하도록 한다.
