[최단경로] 다익스트라

최단 거리를 구하는 알고리즘

 

 

조건

 가중치가 모두 양수

다익스트라 알고리즘은 그리디 기반의 알고리즘으로 최소 거리에 최소 거리를 붙여가면 최종적으로 길을 찾기 때문에 음수 가중치는 고려하지 못한다.

 

 

의사 코드

for each vertex v:
	dist [v] = ∞
	prev [v] = none
	dist [source] = 0
set all vertices to unexplored 
while destination not explored:
	v = least-valued unexplored vertex
	set v to explored for each edge (V, w):
	if dist[v] + len (v, w) < dist[w]:
		dist [w] = dist[v] + len (V, w)
		prev [w] = v

 

1. 노드까지의 최단 거리를 저장하는 dist배열

2. 모든 거리를 무한으로, 시작 지점은 0으로 초기화

3. visited 배열등을 사용하여 미방문으로 초기화

 

반복

4. 방문하지 않고 거리가 최소인 노드를 찾는다.

5. 인접노드까지의 거리 갱신 및 방문처리

 

 

 

 

 

적용되는 이유

다익스트라 알고리즘은 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 기록한다.

여기서 DP가 적용되는 이유는, 굳이 한 번 최단 거리를 구한 곳은 다시 구할 필요가 없기 때문이다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할 때 최단 거리를 효율적으로 구할 수 있다.

 

 

방문하지 않고 거리가 최소인 노드를 찾을 때 - 힙 사용하기

 

visited을 사용하여 모든 노드를 탐색하지 않고, 방문하지 않고 거리가 최소인 노드를 찾는 방법으로 우선순위큐를 이용하는 방법이 있다. 이 방법을 사용하면 시간을 많이 줄일 수 있다.

 

  function Dijkstra(Graph, source):
      dist[source] ← 0                                    // 초기화
      create vertex set Q

      for each vertex v in Graph:
          if v ≠ source
              dist[v] ← INFINITY                          // 소스에서 v까지의 아직 모르는 길이
          prev[v] ← UNDEFINED                             // v의 이전 노드

         Q.add_with_priority(v, dist[v])


     while Q is not empty:                          // 메인 루프
         u ← Q.extract_min()                         // 최고의 꼭짓점을 제거하고 반환한다
         for each neighbor v of u:              // Q에 여전히 남아 있는 v에 대해서만
             alt ← dist[u] + length(u, v)
             if alt < dist[v]
                 dist[v] ← alt
                 prev[v] ← u
                 Q.decrease_priority(v, alt)

     return dist, prev

 

코드 예시

import sys
import heapq
input = sys.stdin.readline


V, E = map(int, input().split())
K = int(input())
INF = sys.maxsize

adjList = [[] for _ in range(V+1)]

for _ in range(E):
    s, e, w = map(int, input().split())
    adjList[s].append((e, w))
def dijkstra(s):
    que = []
    heapq.heappush(que, (0, s))
    dist = [INF] * (V+1)
    dist[s] = 0

    while que:
        cost, x = heapq.heappop(que)
        if dist[x] < cost:
            continue
        for v, w in adjList[x]:
            w += cost
            if w < dist[v]:
                dist[v] = w
                heapq.heappush(que, (w, v))
    return dist

dist = dijkstra(K)
for i in range(1, V + 1):
    if dist[i] < INF:
        print(dist[i])
    else:
        print("INF")

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

1753번: 최단경로

 

 

x dist

1 [INF, 0, 2, 3, INF , INF ]
2 [ INF , 0, 2, 3, 7, INF ]
3 [ INF , 0, 2, 3, 7, INF ]
4 [ INF , 0, 2, 3, 7, INF ]

 

 

참고

 

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98