다익스트라 알고리즘 '한 지점에서 다른 특정 지점까지의 최단경로'
플로이드워셜 알고리즘 '모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구해야 하는 경우'
플로이드 워셜 알고리즘은 단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행한다.
따라서 O(N^3)의 시간복잡도를 가진다.
- [***모든 노드에서 다른 모든 노드까지]***의 최단 경로를 모두 계산한다.
- Floyd - Warshall 알고리즘은 다익스트라 알고리즘과 마찬가지로 “단계별로 거쳐가는 노드를 기준”으로 알고리즘을 수행한다.
- 다만,
매 단계마다, “방문하지 않은 노드 중” “최단 거리를 갖는 노드 찾기” 과정이 필요하지는 않다.
- 다만,
- 2D 테이블에, [최단 거리 정보]를 저장한다.
- 왜냐하면 [모든 노드] —> [모든 노드] 까지의 최단 경로를 모두 탐색해야 하기 때문임.
- [다익스트라] 의 경우는, [ 1D table상에서, 가장 최소 값인 노드를 뽑아] 서, [그래프 정보를 활용] 하였던 것과 다르다.
- DP 유형에 속한다. (??)
- 2차원 테이블에 기록되어있는 값을 점화식에 따라서 갱신한다는 점에서 다이나믹 프로그래밍에 속한다.
- 점화식에 맞게 3중 반복문을 이용해서 2차원 테이블을 갱신해주는 방식으로 동작한다.
- 구현난이도는 다익스트라 알고리즘보다 쉬운 편.
- 모든 노드 →다른 노드까지의 최단 거리 구하는 과정에서 시간복잡도는 O(n^3)이다.
- 따라서 노드의 개수가 적은 과정에서 효과적으로 사용가능.
- 노드개수 , 간선개수 많은 경우는 다익스트라 알고리즘 사용할 것
다음 처럼 초기 테이블을 설정할 수 잇다.
출발/도착 | 1번 | 2번 | 3번 | 4번 |
1번 | 0 | 4 | INF | 6 |
2번 | 3 | 0 | 7 | INF |
3번 | 5 | INF | 0 | 4 |
4번 | INF | INF | 2 | 0 |
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2
- 테이블
- 맨 처음 초기화 : 인접노드에 대한 값만을 갖는다. / 나머지 노드 : 무한 의 값을 assign.
- 이후, 각 노드에 대해 각각, 각 노드를 거쳐가는 경우를 확인하여 전체 테이블을 갱신
STEP 1) 4개의 노드가 존재하고 7개의 입력값이 주어지는 식을 구현,
import sys
'''
4 7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2
'''
N, M = map(int ,input().split())
graph = [[sys.maxsize for _ in range(N)] for _ in range(N)]
for i in range(N):
A = list(map(int, input().split()))
위의 결과를 만들기 위해 3중 for문을 이용한다.
import sys
'''
4 7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2
'''
N, M = map(int ,input().split())
graph = [[sys.maxsize for _ in range(N)] for _ in range(N)]
for i in range(M):
A = list(map(int, input().split()))
graph[A[0]-1][A[1]-1] = A[2]
for i in range(N):
graph[i][i] = 0
for i in range(N):
for j in range(N):
for k in range(N):
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
for i in graph:
print(i)
성능분석
- 노드의 개수가 N개일때 알고리즘 상으로 N번의 단계를 수행하는데
- 각 단계마다 O(N^2)의 연산을 통해, 현재 노드를 거쳐 가는 모든 경로를 고려한다.
- 따라서, 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)입니다.
- 따라서, 실제 플로이드 워셜이 사용되야 하는 경우 : 노드의 개수가 500개 이하로, 작은 개수인 경우!!
- 500 500 500은 1억이 넘어가기 때문에.. 시간제한이 넉넉하지 않으면 이마저도 시간 초과 판정 받을 수가 있다.
- 따라서 최단 거리 문제 출제시, 다익스트라, 플로이드 워셜 중 어느 것이 적절한지는 문제마다 고민하고, 그 고민 후, 적절한 알고리즘을 선택해야할것.
'알고리즘 > GRAPH' 카테고리의 다른 글
백준 17837번) 새로운 게임2 - 파이썬 (0) | 2022.10.01 |
---|---|
(최단경로알고리즘) 전보, 다익스트라(PYTHON) (0) | 2021.12.23 |
미래 도시(PS) (0) | 2021.12.20 |
최단 경로 알고리즘(다익스트라 알고리즘, 파이썬) (0) | 2021.12.19 |