다익스트라 알고리즘(최단경로 알고리즘), python

 

다익스트라 알고리즘이란?

 

그래프의 어떤 한 정점에서 출발하여 다른 정점까지 갈 수 있는 가장 짧은 경로를 찾는 알고리즘이다.

 

 

출발점에서 도착점까지의 가장 짧은 경로를 저장할 배열 d를 만들고,

탐색하지 않은 정점 중에서 d값이 가장 작은 정점을 탐색해 

d [인접한 정점] 과 d [현재 정점] + (현재 정점에서 인접한 정점까지의 길이) 중 더 짧은 경로를 업데이트해주면 된다.

 

 

 

 

 

다익스트라 알고리즘으로 최단경로를 구하는 과정

 

정점의 개수가 5개이고 간선의 정보가 다음과 같다.

 

출발	도착	가중치
0	1	4
0	2	2
1	2	5
1	3	10
2	4	3
4	3	4

 

위 그래프에서 0번 정점에서 출발하여 다른 정점으로의 최단경로를 구하려 한다.

 

 

 

 

먼저 각 정점까지의 최단경로를 저장할 배열 d를 만든다. 초기값은 INF로 설정한다.

출발점 정점에서 자기 자신까지의 거리는 0이므로 d [출발점] = 0을 해준다.

정점 번호	0	1	2	3	4
d	0	INF	INF	INF	INF

 

 

 

 

 

 

 

정점 번호	0	1	2	3	4
d	0	INF->4	INF->2	INF	INF

 

0번 정점에서는 1번, 2번 정점으로 갈 수 있다. 

d [1]은 기존에 최단경로 (d [1] = INF)와 비교해서 0번에서 오는 경로(d [0] + 4 = 4)가 더 작으므로 갱신해 준다.

d [2]은 기존에 최단경로 (d [2] = INF)와 비교해서 0번에서 오는 경로(d [0] + 2 = 2)가 더 작으므로 갱신해 준다.

 

 

 

 

 

 

 

이제 d배열에서 탐색하지 않은 정점 중 d값이 가장 작은 정점을 선택한다.

최솟값은 2 이므로 다음에 선택할 정점은 2번이다.

정점 번호	0	1	2	3	4
d	0	4	2	INF	INF->5

 

2번 정점에서는 4번 정점로 갈 수 있다. 

d [4]은 기존에 최단경로 (d [4] = INF)와 비교해서 2번에서 오는 경로(d [2] + 3 = 5)가 더 작으므로 갱신해 준다.

 

 

 

 

 

 

 

탐색하지 않은 정점 중에 d값이 가장 작은 정점은 1번 정점이다.

정점 번호	0	1	2	3	4
d	0	4	2	INF->14	5

 

1번 정점에서는 2번, 3번 정점으로 갈 수 있다. 

d [2]은 기존에 최단경로 (d [2] = 2)와 비교해서 1번에서 오는 경로(d [1] + 5 = 9)가 더 크므로 갱신하지 않는다.

d [3]은 기존에 최단경로 (d [3] = INF)와 비교해서 1번에서 오는 경로(d [1] + 10 = 14)가 더 작으므로 갱신해 준다.

 

 

 

 

 

 

 

다음으로 d값이 가장 작은 정점은 4번이다. 

정점 번호	0	1	2	3	4
d	0	4	2	14 ->9	5

 

4번 정점에서는 3번 정점로 갈 수 있다. 

d [3]은 기존에 최단경로 (d [3] = 14)와 비교해서 1번에서 오는 경로(d [4] + 4 = 9)가 더 작으므로 갱신해 준다.

 

 

 

 

 

 

다음으로 d값이 가장 작은 정점은 3번이다. 

정점 번호	0	1	2	3	4
d	0	4	2	14 ->9	5

 

3번에서 갈 수 있는 정점은 없으므로 넘어간다.

 

 

 

 

 

 

이렇게 모든 정점을 전부 탐색하고 나온 d 배열이 출발점에서 각 정점까지의 가장 짧은 경로가 된다.

정점 번호	0	1	2	3	4
d	0	4	2	9	5

 

 

 

 

 

 

 

python 구현

 

다익스트라 알고리즘은 힙을 사용하여 구현할 수 있다.

최소힙에 (현재까지 계산한 거리, 정점번호)를 넣어주면 힙 최상단에는 d값이 가장 작은 정점이 있게 된다.

만약 힙에서 꺼낸 ' 현재까지 계산한 거리'가 이미 d에 저장된 값보다 크다면, 탐색할 필요가 없다.

왜냐하면 이미 더 짧은 경로가 있으므로 더 긴 경로는 탐색하지 않아도 되기 때문이다.

 

먼저 d배열의 초기값을 설정하고 힙을 생성하고 출발점을 넣어준다

from heapq import*

heap = []
# 최단 경로는 0, 출발정점은 0
heappush(heap,(0,0))
# d배열의 초기값은 INf, 출발점은 0
d = [float('inf')]*(n+1)
d[0] = 0

 

 

그다음 최소힙에서 하나를 꺼내 인접한 정점들을 업데이트해준다.

while heap:
    # 거리가 제일 짧은 정점을 꺼낸다
    dist, cur = heappop(heap)
	
    # 현재까지 계산한 거리가 d에 저장된 값보다 크다면 넘어간다.
    if dist > d[cur]:
        continue
	
    # d[인접한 정점]보다 d[현재 정점] + 현재 정점에서 인접한 정점까지의 길이가 작다면
    # 현재 정점을 거쳐 인접한 정점으로 가는게 더 짧은경로이므로 업데이트하고 힙에 넣어준다.
    for next,w in graph[cur]:
        if d[next] > d[cur] + w:
            d[next] = d[cur] + w
            heappush(heap, (d[next], next))

 

 

 

d배열에서는 최단 경로의 길이만 구할 수 있다.

만약 최단 경로의 루트를 알고 싶으면, 해당 정점이 갱신될 때 어디로부터 왔는지를 따로 저장해 주면 된다.

while heap:
    dist, cur = heappop(heap)

    if dist > d[cur]:
        continue

    for next,w in graph[cur]:
        if d[next] > d[cur] + w:
            d[next] = d[cur] + w
            # 최단경로가 갱신되었다면, 어디 정점에서 왔는지 prev값에 저장해준다.
            prev[next] = cur
            heappush(heap, (d[next], next))

 

 

그리고 목적지부터 출발점까지 이전 정점을 역추적하면 목적지까지의 최단 경로의 루트를 구할 수 있다.

route = []

cur = 3

# 목적지부터 출발점이 아닐때까지 이전 정점을 역추적
while cur != 0:
	print(cur)
    cur = prev[cur]

# 출발점을 추가하고 뒤집으면 된다
route.append(0)
route.reverse()

 

 

 

 

 

 

다익스트라를 사용하여 해결할 수 있는 문제

 

[백준] 2211 네트워크 복구

[백준] 2211 네트워크 복구