[BOJ] 1753번 - 최단경로(Python) + Dijkstra Algorithm

🗒️ 다익스트라 알고리즘 (Dijkstra Algorithm)

• 모서리 또는 정점에 가중치가 부여된 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘
  • 가중치가 없는 그래프에서의 최단경로는 BFS를 사용!
• 어떤 시작점 s가 주어졌을 때, 그 정점에서 시작하여 다른 모든 정점으로 가는 최단 경로를 찾는다.
• 단, 음수인 가중치가 없는 경우에만 쓸 수 있다.

음수의 가중치가 있을 경우

실제 최단 경로는 우리집에서 옆집으로 이동하는 것이지만, 우리집에서 은행을 거쳐 가는 것이 비용상 이득이 되는 경우가 발생한다.

즉, 값이 음수인 모서리가 있으면 경로를 만들어가는 도중에 아주 작은 음수 값을 가지는 모서리가 있어서 이미 트리에 들어있는 최단 경로와 전혀 다른 경로를 만들어야 할 수 있다.

동작 과정(간선 완화 과정)

1. 모든 꼭짓점을 미방문 상태로 표시 : visited
2. 초기점을 0으로, 다른 모든 꼭짓점을 무한대로 설정 : distance
3. 현재 꼭짓점 k에서 미방문 인접 꼭짓점 v을 찾아 그 거리를 계산
    : distance[k] + weight(k와 v 사이의 가중치)
    만약 계산한 거리가 현재 저장되어 있는 값보다 작으면 변경
    : if (distance[k] + weight < distance[v]) → distance[v] = distance[k] + weight
4. 만약 현재 꼭짓점에 인접한 모든 미방문 꼭짓점까지의 거리를 계산한 경우 → visited[k] = True

→ 두 꼭짓점 사이의 경로를 찾는 경우
     : 도착점이 방문한 상태로 표시되면 멈추고 알고리즘을 종료한다.
→ 완전 순회 경로를 찾는 경우
     : if (미방문 집합에 있는 꼭짓점들의 distance 중 최솟값이 무한대)
            출발점과 미방문 집합 사이에 연결이 없는 경우이므로 멈추고 알고리즘을 종료
       else
            distance가 가장 작은 다음 미방문 꼭짓점을 "현재 위치"로 선택하고 3단계로 되돌아간다.

즉, 다음 정점을 선택하는 기준은 시작 정점에서 부터 경로(distance)가 가장 짧은 정점이다!

이를 선택할 방법은 반복문을 사용거나 우선순위 큐를 사용할 수 있다.

이에 대한 예시는 아래의 풀이에서 확인할 수 있다.

 

[참고]

https://ko.wikipedia.org/wiki/다익스트라_알고리즘

https://code-lab1.tistory.com/29

https://justkode.kr/algorithm/python-dijkstra/

---

🛠️ 문제 🛠️

---

🍀 풀이 🍀

1. 반복문을 사용한 풀이

import sys

v, e = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline()) # 시작 정점
graph = [[] for _  in range(v+1)]

for _ in range(e) :
    a, b, w = map(int, sys.stdin.readline().split())
    graph[a].append((b, w))

def dijkstra(graph, s, v) :
    visited = [False] * (v+1)
    distance = [sys.maxsize] * (v+1)
    
    distance[s] = 0
    current = s
    
    for _ in range(v) :
        visited[current] = True
        for vertex, weight in graph[current] :
            distance[vertex] = min(distance[vertex], distance[current] + weight)

        # distance가 가장 짧은 정점 선택! - 반복문 이용
        min_dist = sys.maxsize
        for i in range(1, v+1) :
            if visited[i] == False and min_dist > distance[i] :
                current = i
                min_dist = distance[i]
    
    for i in range(1, v+1) :
        if distance[i] == sys.maxsize :
            print("INF")
        else :
            print(distance[i])

dijkstra(graph, k, v)

위에서 정리한 간선 완화 과정을 토대로 작성한 코드이다.

정답을 도출하긴 했지만 시간초과가 발생했다.

코드를 보면 모든 정점의 distance를 확인하고 그 중 가장 짧은 정점을 선택하기 때문에 시간 복잡도가 O(V^2)이다.

 

2. 우선순위 큐를 사용한 풀이

import sys
import heapq

v, e = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline()) # 시작 정점
graph = [[] for _  in range(v+1)]

for _ in range(e) :
    a, b, w = map(int, sys.stdin.readline().split())
    graph[a].append((b, w))

def dijkstra(graph, s, v) :
    distance = [sys.maxsize] * (v+1)
    queue = []
    
    distance[s] = 0
    heapq.heappush(queue, [distance[s], s])
    
    while queue :
        # distance가 가장 짧은 것부터 pop - 우선순위 큐 사용
        dist, vertext = heapq.heappop(queue)
        
        if distance[vertext] >= dist :
            for nv, w in graph[vertext] :
                if distance[nv] > dist + w :
                    distance[nv] = dist + w
                    heapq.heappush(queue, [distance[nv], nv])
    
    for i in range(1, v+1) :
        if distance[i] == sys.maxsize :
            print("INF")
        else :
            print(distance[i])

dijkstra(graph, k, v)

이 코드는 시간을 단축하기 위해 자료구조 중 heap을 사용한 방법이다.

 

모든 간선은 한 번씩 검사되므로 전체 O(|E|)의 시간이 걸린다.
우선순위 큐가 가장 커지는 최악의 시나리오는 그래프의 모든 간선이 검사될 때마다 distance가 갱신되고 우선순위 큐에 정점의 번호가 추가되는 것으로, 우선순위 큐에 추가되는 원소의 수는 최대 E개이고, 삽입연산이 일어난다는 점에서 전체 시간 복잡도는 O(|E||log|E|)가 됨을 알 수 있다.
대개의 경우 그래프에서 |E| < |V|^2 이기 때문에 O(log|E|)=O(log|V|)라고 볼 수 있다.

따라서 시간 복잡도는 O(|E||log|V|)가 된다.

 

[참고]

https://ds-jungsoo.tistory.com/7