최단경로 : 플로이드 워셜 - 이론정리 (미완)
플로이드워셜
- 사용 : 모든 지점에서 다른 모든지점까지의 최단경로 모두 구하는 경우
- 전제조건 :
- 시간복잡도 : O()
- 구현개념 :
다익스트라와의 차이점
다익스트라 | 플로이드워셜 |
---|---|
하나의 지점 ~ 다른 모든 지점까지의 최단경로 모두 구함 | 모든 지점 ~ 다른 모든 지점가지의 최단경로 모두 구함 |
출발노드가 1개이므로, 결과저장위해 1차원 리스트 활용 | 출발노드가 N개이므로, 결과저장위해 2차원 리스트 활용 |
그리디 알고리즘(그때그때 최단거리 선택) | 다이나믹 프로그래밍(노드가 N개일때, N번만큼 단계 반복하며 '점화식에 맞게' 2차원 리스트 갱신) |
|
구현 아이디어
= min(A에서 B로가는 최소비용, A에서 K를 거쳐 B로가는 최소비용)
동작 과정
[step_0] 그래프의 노드와 간선에 따라 최단 거리 테이블을 갱신한다.
[step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.
[step 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.
[step ~] 3번, 4번, ... 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.
시간복잡도 상세
구현 코드
INF = int(1e9)
# 노드의 갯수 및 간선의 갯수 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)을 만들고, 모든 값을 무한으로 초기화
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) :
# 도달할 수 없는 경우, INF 출력
if graph[a][b] == INF :
print("INF", end = " ")
else :
print(graph[a][b], end=" ")
print()
레퍼런스
Author And Source
이 문제에 관하여(최단경로 : 플로이드 워셜 - 이론정리 (미완)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yesterdaykite/최단경로-플로이드-워셜-이론정리-미완저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)