3. Dijkstra
: 그래프에서 한 정점(노드)에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘,
이 때 도착 정점 뿐 아니라, 그 과정에서 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. (매번 최단 경로의 정점을 선택해 탐색을 반복하니까, 그리고 음의 가중치 포함X)
- Greedy+DP
*MST는 하나의 그래프에서 모든 노드를 포함하며 ‘최소 비용으로 연결된 트리’(즉 최소 연결 구조)를 구성하는 반면, Dijkstra는 단일 출발점에서 다른 모든 노드까지의 ‘최단 경로’를 찾는다.
[그래프와 트리의 차이?: 트리는 부모-자식 관계를 가지며 사이클이 없고, 각 노드 사이 유일한 경로가 존재하는 특수한 조건의 그래프(그래프는 이런 제약이 없고 더 다양한 구조를 가짐]
- [과정]
- 출발 노드/도착 노드 설정 후 ‘최단 거리 테이블’을 초기화
- 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 그 중 거리가 가장 짧은 노드를 선택(선택한 노드는 방문 처리)
- 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용을 계산해 ‘최단 거리 테이블’ 갱신
- 2-3 과정 반복
-
구현 방법: 인접 행렬, 우선순위 큐
-
우선순위 큐 구현
: 본래 최단 거리 테이블과 방문 처리 테이블이 필요했는데, 우선순위 큐를 이용하면 알아서 가장 최단 거리인 노드를 앞으로 정렬해주기 때문에 기존에 기록한 최단 거리보다 크다면 그냥 무시해주면 됨 -
개선된 다익스트라 알고리즘? 힙 활용
4. 플로이드 와샬(Floyd Warshall)
: 그래프의 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
- DP 사용
- 다만, 다익스트라와 다르게 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않음(또한 음의 가중치도 허용)
- 다익스트라: 가장 적은 비용을 가진 정점을 기준으로 최단 거리를 구하는 것
- 플로이드 와샬: 거쳐가는 정점을 기준으로 최단 거리를 구하는 것
- 모든 정점에 대한 경로를 계산하므로 2차원 배열 사용, 3중 for문으로 시간 복잡도는 O(n^3)
- 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인
- a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사
- 점화식: D[a][b] = min(D[a][b], D[a][k]+D[k][b])
- -> 기존 D[a][b] 경로보다 [k]를 거쳐 가는 값이 더 작다면 값을 새로 갱신
- 예를 들어 k=1로 두면, (2->3), (2->4), (3->4)… 모든 경로의 경우에 수에 1번 노드를 거쳐가는 경우를 고려하는 것
- 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인
- [구현]
- 2차원 리스트로 그래프를 표현하고, 자기 자신->자기 자신은 0으로 초기화
- 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
- 점화식에 따라 알고리즘 수행
- 힙 자료구조
- 속성: 부모 노드와 자식 노드의 대소 관계, 이 속성으로 힙에선 가장 낮거나 높은 노드가 루트에 오게 됨(대신 형제 노드 사이엔 대소 관계x)
- 최소힙: 부모 노드 < 자식 노드
- 최대힙: 자식 노드 < 부모 노드
- 힙 함수 활용
- heapq.heappush(heap, item): item을 heap에 추가
- heapq.heappop(heap): heap에서 가장 작은 원소를 pop & return
- heapq.heapify(x): 리스트 x를 즉각 heap으로 변환(O(N)
- heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙으로 사용하고 싶으면 push할 때/pop 할 때 음수화해서 넣고 가져오면 됨
