다익스트라 알고리즘에서 실제 최단 경로 구하기

1. 실제 최단 경로 역추적

 

지금까지 다익스트라 알고리즘에선 최단 경로로 가는데 걸리는 가중치의 합을 구해왔는데, 실제 최단 경로가 궁금할 수도 있다

 

어떻게 하면 구할 수 있을까?

 

결론부터 말하자면 경로를 역추적해서 구한다

 

어떤 정점 A에서 목적지 B로 가는데, "A,C,D,E,F,G,B로 가는게 최단 경로다" 이렇게 순방향으로 구하지 않고,

 

다익스트라 알고리즘에서 테이블에서 최단 거리를 가진 정점 u를 선택할때,

 

u와 인접한 정점 b를 선택하는데, b의 거리가 테이블에서 갱신될때

 

"b와 가장 가까운 정점이 u이다"라고 테이블에 저장을 해놓는다

 

모든 과정이 종료되면 목적지 B와 가장 가까운 정점이 G이고,

 

G와 가장 가까운 정점이 F이고

 

F와 가장 가까운 정점이 E이고,

 

...

 

C와 가장 가까운 정점이 A이고

 

A와 가장 가까운 정점은 없다

 

그래서 A,C,D,E,F,G,B가 최단 경로다..

 

이런 식으로 구한다

 

 

2. 예시를 통해 이해하는 다익스트라 최단 경로 역추적

 

실제 다익스트라 알고리즘을 수행하면서, 최단 경로 역추적까지 수행해보자

 

 

1번에서 6번까지 가는데 실제 최단 경로를 구해보자.

 

dist 배열에는 각 노드까지 가는데 최단 거리를 저장하고, prev 배열에는 각 노드로 가는데 가장 가까운 거리의 정점을 저장한다

 

초기에는 dist 배열은 무한을 저장시키고, prev 배열에는 0을 저장시킨다.

 

1번부터 n번까지의 노드가 존재한다고 가정한다. 0번부터 존재한다면.. prev에 -1을 저장시키든지 응용하면 되겠다

 

최초 시작에는 시작점 1번의 dist 값과 prev 값은 0으로 시작한다

 

우선순위 큐에 (최단거리, 노드)를 넣어서 다익스트라 알고리즘을 수행

 

 

최초 (0,1)이 들어갈 것이고, (0,1)을 빼면서 알고리즘이 수행된다

 

1번과 인접한 2,3,4 노드를 검사한다.

 

2,3,4와의 거리가 각각 2,5,1이므로, 최단거리 테이블을 갱신한다

 

이때, 최단거리 테이블이 갱신된 노드는 그 노드와 가장 가까운 정점도 함께 저장한다

 

2,3,4와의 최단 거리가 각각 2,5,1로 저장되었고 그 말은 2,3,4와 가장 가까운 노드는 현재 1번이라는 소리다.

 

그래서 prev에 2,3,4번에는 1을 저장한다

 

우선순위 큐에서 최단 거리가 가장 가까운 (1,4)가 나온다. 노드 4를 먼저 검사한다

 

 

3번과의 거리는 4이고 5번과의 거리는 2이다. 최단 거리 테이블이 각각 갱신되므로

 

prev 배열도 같이 갱신을 한다

 

이 말은 3번 노드와 가장 가까운 정점은 4번이라는 소리다.

 

그리고 5번 노드와 가장 가까운 정점은 4번이라는 소리다.

 

그리고 우선순위 큐에서 거리가 가장 가깝고, 노드 번호가 작은 (2,2)가 나와 2번 노드를 검사한다

 

 

 

이제 2번 노드에 대해 검사를 수행한다. 2번과 인접한 정점은 3번과 4번이고 각각 5와 4인데

 

최단거리 테이블에서 현재 3번과 4번까지 최단거리는 각각 4와 1로 최단거리가 갱신되지 않는다

 

따라서 prev 배열도 같이 갱신하지 않는다

 

다음으로 우선순위 큐에서 나오는 노드는 (2,5)로 5번 노드이다. 5번 노드에 대해 인접 노드를 검사한다

 

 

 

5번과 인접한 정점은 각각 3,6번이다. 5번까지 최단거리는 현재 2이므로 3번,6번까지 거리를 구하면 각각 3,4가 된다.

 

현재 최단거리 테이블에 3번과 6번까지 최단거리는 4와 무한이므로, 더 짧은 거리를 찾았다.

 

그러므로 최단거리 테이블을 갱신한다.

 

최단거리 테이블을 갱신했으므로 prev 배열도 갱신한다.

 

3번 노드와 가장 가까운 정점은 5번이라는 소리이고, 6번 노드와 가장 가까운 정점도 5번이라는 소리다.

 

 

 

다음 우선순위 큐에서 나오는 노드는 거리가 가장 가까운 (3,3)이다.

 

3번 노드와 인접한 노드는 2번과 6번이다. 현재 3번까지 최단 거리는 3이다.

 

2번까지 거리는 6이고, 6번까지 거리는 8이 된다. 하지만 최단 거리 테이블에서 2번과 6번까지 최단 거리는 각각 2와 4이다.

 

그러므로 최단거리 테이블을 갱신하지 않는다.

 

마찬가지로 prev 배열도 갱신하지 않는다

 

 

마지막 6번 노드는 인접한 노드가 존재하지 않아 알고리즘이 종료된다.

 

그래서 최종 테이블은.. 다음과 같다.

 

 

1번에서 6번까지 실제 최단 경로를 구하고 싶다. 위 dist 테이블에서 1번에서 시작해서 6번까지 최단 거리는 4라는 것을 알 수 있다.

 

prev 배열은 무엇을 뜻할까?

 

###################################################################################

 

목적지인 6번부터 시작한다.

 

6번에 저장된 5는, 6번과 가장 가까운 정점이 5번이라는 말이다. 6 <- 5

 

그 다음 5번으로 넘어가서 5번에 저장된 prev 값은.. 4이다. 5번과 가장 가까운 정점은 4번이라는 소리다.

 

6 <- 5 <- 4

 

그 다음 4번으로 넘어가서 4번에 저장된 prev값은..1이다. 4번과 가장 가까운 정점은 1번이라는 소리다.

 

6 <- 5 <- 4 <- 1

 

그 다음 1번으로 넘어가서 1번에 저장된 prev 값은 0이다.. 하지만 0번 노드는 존재하지 않는다.(1번부터 n번까지 노드가 있다고 가정함)

 

따라서 6 <- 5 <- 4 <- 1을 역순으로 배열한, 1 -> 4 -> 5 -> 6이 1번에서 6번까지의 실제 최단 경로다.

 

###################################################################################

 

실제 그림으로도 일치한다는 것을 알 수 있다

 

 

3. 연습 문제

 

11779번: 최소비용 구하기 2 (acmicpc.net)

11779번: 최소비용 구하기 2

 

노드 A에서 B로 가는데 최소 비용과 실제 최단 경로를 같이 구하는 문제

 

 

4. 풀이

 

위에서 설명한 알고리즘을 그대로 구현하면 정답

 

최단 경로는 여러가지가 있을 수 있어서.. 사람마다 답이 다를 수도 있다.. 그래서 문제로 자주 출제되지는 않는듯?

 

import heapq
from sys import stdin

def dijkstra(start):

    q = []

    heapq.heappush(q,(0,start))

    distance[start] = 0
    
    #시작 지점과 가장 가까운 노드는 0이라고 초기화
    prev[start] = 0 

    while q:
        
        dist,u = heapq.heappop(q)

        if distance[u] < dist:
            
            continue
        
        for b,c in graph[u]:
            
            cost = dist + c

            if cost < distance[b]:
                
                distance[b] = cost

                heapq.heappush(q,(cost,b))
                
                ## b까지의 최단 거리가 갱신된다면, 
                ## b와 가장 가까운 노드는 u이다.
                prev[b] = u
    

    return prev,distance
        

n = int(stdin.readline())

m = int(stdin.readline())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    
    a,b,c = map(int,stdin.readline().split())

    graph[a].append((b,c))

start,goal = map(int,stdin.readline().split())

INF = 100000000000000

distance = [INF]*(n+1)

##최단 경로를 역추적하기 위한 배열 초기화
prev = [0]*(n+1) 

dir,distance = dijkstra(start)

print(distance[goal])

##실제 최단 경로 역추적하기

s_path = [goal]

##목적지부터 시작
prev_node = goal

while 1:
    
    ##현재 노드와 가장 가까운 이전 노드 prev_node
    prev_node = prev[goal]
    
    ##반복을 통해 이전 노드가 0이라면..
    ##이전 노드가 없다는 말이므로
    ##현재 노드가 출발 노드니까 반복문 탈출
    
    if prev_node == 0: 
        
        break
    
    ##이전 노드가 0이 아니라면..
    else:
        
        ##현재 노드를 최단 경로 리스트에 넣어두고
        s_path.append(prev_node)
        
        ##다음 경로 역추적을 위해 현재 노드를 갱신한다
        goal = prev_node

print(len(s_path))

##추적한 경로를 역순으로 배열하면 실제 최단 경로
print(*s_path[::-1])

"""
5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

4
3
1 3 5
"""