[알고리즘] 최단 경로 알고리즘

최단 경로 알고리즘

: 가장 짧은 경로를 찾는 알고리즘

 

- 다익스트라

- 플로이드 워셜

- 벨만 포드

 

다익스트라 최단 경로 알고리즘

: 특정한 노드에서 다른 노드를 가는 최단 경로

- 음의 간선 X

 

1. 출발 노드

2. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택

3. 최단 거리 테이블 갱신

4. 2, 3번 반복

 

구현 방법

1. 간단, 느린 방법 - 매번 최단 거리가 가장 짧은 노드 순회 + 테이블 갱신

2. 복잡, 빠른 방법 - 힙 이용

=> 힙(Heap)을 이용해 우선순위 큐를 구현하고 이를 최단 거리가 가장 짧은 노드를 구하는 과정에 이용

 

heapq 라이브러리 -> 삽입과 삭제를 O(logN)에 수행

다익스트라 알고리즘 전체 시간 복잡도 = O(ElogV)

 

 

플로이드 워셜 알고리즘

: 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용

<=> 다익스트라 : 한 지점에서 다른 특정 지점까지의 최단 경로

 

- 2차원 리스트에 최단 거리 정보 저장 => 모든 노드에서 다른 모드 노드로가는 최단 거리 정보를 담기 때문에

- 현재 보고있는 노드를 거쳐 가는 모든 노드 쌍을 계산 ex) A노드 -> B노드로 바로 가는 경우 vs A노드 -> 1번 노드 -> B노드로 거쳐서 가는 경우를 비교해 더 짧은 거리로 갱신