다익스트라 (Dijkstra)

개념

다익스트라 알고리즘은 Single Source shortest path problem으로

하나의 정점에서 다른 모든 정점까지 최단 경로를 구할 때 주로 사용됩니다.

이때, 간선의 가중치는 only 양수가 전제조건입니다. (음의 가중치 X)

실제, 현실 세계에서는 음의 가중치는 일반적이지 않기에 현실에 적합한 알고리즘이라고 볼 수 있습니다.

 

시뮬레이션

그래프를 인접행렬로 표현

▶ dist[] 배열 초기화

※ 시작 정점 = [5] 가정. ← 방문 표시

- 정점 [5]와 연결된 정점 [2], [4]와 정점 [5] 자체에 대한 dist[] 초기화

 

▶ 방문하지 않은 정점 가장 비용이 적은 정점 [4] 선택 ← 방문 표시

    [4]번 정점과 연결되었으면서 동시에 아직 한번도 방문하지 않은 정점 [2], [3]에 대한 최단 거리를 구합니다.

    dist[2] = Min(dist[2], dist[4] + adj[4][2]) = Min(4, 2 + 1) = 3

    dist[3] = Min(dist[3], dist[4] + adj[4][3]) = Min(INF, 2 + 1) = 3

▶ 방문하지 않은 정점들 중 가장 비용이 적은 정점이 두 개이므로 그중 낮은 번호의 정점 [2] 선택 ← 방문 표시

    [2]번 정점과 연결되었으면서 방문하지 않은 정점 [1]에 대한 최단 거리를 구합니다.

    dist[1] = Min(dist[1], dist[2] + adj[2][1]) = Min(INF, 3 + 3) = 6

 

▶ 방문하지 않은 정점 가장 비용이 적은 정점 [3] 선택 ← 방문 표시

    [3]번 정점과 연결된 정점[4]는 이미 방문했으므로 추가적인 처리 X

 

▶ 방문하지 않은 정점이 [1]뿐이므로 다익스트라 알고리즘 종료 (추가 처리 불필요)

 

정점 [5]에서 각 정점에 이르는 최단거리

- 정점 [1]까지 최단 거리 비용: 『 6 』

- 정점 [2]까지 최단 거리 비용: 『 3 』

- 정점 [3]까지 최단 거리 비용: 『 3 』

- 정점 [4]까지 최단 거리 비용: 『 2 』

 

※ 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 그대로 사용 → DP

   여러 간선 중 최소 비용 경로 이용 → Greedy

 

관련 내용

* (선형) 다익스트라 이용한 문제 → 시간복잡도 O(N2)

    - [BOJ] 1916 최소비용 구하기 (인접행렬로 그래프 구현)

[BOJ] 백준 1916 최소비용 구하기

* 우선순위 큐를 이용한 문제 → 시간복잡도 O(N logN)

    - [BOJ] 1753 최단거리 (인접 리스트로 그래프 구현)

[BOJ] 백준 1753 최단거리

▶ 인접행렬은 메모리를 불필요하게 잡으며, 선형탐색에서 1~N 까지 정점을 전부 순회하기에 비효율적

※ 그래프 구현 (인접 리스트 / 인접 행렬)

그래프 표현 (인접 리스트 / 인접 행렬)

★ [BOJ] 1719 택배 ← 경로 추적 문제(인접리스트 그래프 방식 + 우선순위큐, 선형 방식 둘다 구현)

★ [SWEA] 4007 간담회 참석

★ [SWEA] 3947 가장 짧은 길 전부 청소하기 (경로 추적 + 정점 방문시 경로 갱신 시도)