[알고리즘] Dijkstra's Algorithm

Dijkstra's Algorithm

두 정점 사이의 최단거리를 찾을 때 사용하는 알고리즘

 

 

다익스트라의 핵심 속성 : 최단경로의 모든 부분경로는 최단거리이다

 

 

가중치가 없는 최단거리를 구할 때 DFS, BFS 알고리즘을 사용하지만,

양의 가중치가 있고, 그 가중치가 모두 다를 경우 다익스트라 알고리즘을 사용한다

 

---

 

Dijkstra's Algorithm 동작 과정

 

1. 출발 노드 설정

2. 최단 거리 테이블 초기화

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

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산 후 최단 거리 테이블 갱신

5. 위 과정에서 3번과 4번을 반복

 

---

Dijkstra's Algorithm 구현 소스

 

아래는 다익스트라 알고리즘 문제인 '민준이와 마산 그리고 건우' 소스이다.

https://www.acmicpc.net/problem/18223

18223번: 민준이와 마산 그리고 건우

 

import heapq

V, E, P = list(map(int, input().split()))
adj = [[] for _ in range(V + 1)]


def solution():
    for _ in range(E):
        a, b, c = list(map(int, input().split()))

        # 인접리스트 생성
        adj[a].append((b, c))
        adj[b].append((a, c))

    # 전체 최단거리가 P를 거쳐가는 최단거리와 같다면 건우 구하기 가능
    if dijkstra(1, V) == dijkstra(1, P) + dijkstra(P, V):
        return "SAVE HIM"
    else:
        return "GOOD BYE"


def dijkstra(s, e):
    q = list()
	
    # 1. 출발 노드 설정
    newDist[s] = 0
    heapq.heappush(q, (0, s))   # (거리, 노드) 저장
	
    # 2. 최단 거리 테이블 초기화
    newDist = [1e9] * (V + 1)
    
    while q:
        # 3. 현재 가장 가까운 노드를 pop
        dist, now = heapq.heappop(q)

        # 이미 처리된 적 있는 노드면 무시
        if newDist[now] < dist:
            continue

        for next, cost in adj[now]:
            # 4. 현재노드를 거쳐가는 거리가 더 짧은 경우 갱신
            if newDist[next] > dist + cost:
                newDist[next] = dist + cost
                heapq.heappush(q, (newDist[next], next))
            
    return newDist[e]

print(solution())

 

---

시간복잡도

• 각 정점마다 인접한 간선들을 탐색하는 과정
  각 노드는 최대 한 번씩 방문하기 때문에 그래프의 모든 간선은 최대 한 번씩 검사한다. 따라서 이 과정의 시간 복잡도는 O(E)이다.
• 우선순위 큐에 [거리, 정점] 정보를 넣고 빼는 과정
  최악의 경우는 모든 간선을 검사할 때 마다 거리 값 리스트가 갱신되고, 우선순위 큐에 정보가 저장되는 경우이다. E개의 간선을 검사할 때 마다 우선순위 큐를 유지해야 하므로 이 과정의 시간 복잡도는 O(ElogE)이다.

위 두 과정을 거칠 경우 다익스트라 알고리즘의 총 시간 복잡도는 O(E)+O(ElogE)=O(ElogE) 가 된다.

 

---

reference

https://youtu.be/acqm9mM1P6o

https://velog.io/@adorno10/%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C1-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98