[알고리즘/개념/그래프] Dijkstra 최단경로 알고리즘

Graph를 탐색하는 방법은 엄청 많다. 하지만, 그 중에서도 우리에게 의미가 있는 탐색방법이 있는데, 그 중 하나가 최단경로를 알아내는 것이다. 이것은 현실세계에서도 마찬가지이다. 돌아가는 것보단, 그 누구라도 목적지에 빨리 도달 하고 싶을 것이다.

Thinking

BFS/DFS는 가중치가 있는 그래프에서도 쓸 수 있지만, BFS/DFS는 완전탐색 알고리즘이므로, 결국 모든 노드를 방문해야한다. "어떻게 효율적으로 아래와 같은 가중치가 있는 그래프가 있을 때, 최단 경로를 알아낼 수 있을까" 의 이야기이다.

전제 조건

• Graph는 단방향이든, 양방향이든 가중치가 있는 그래프를 대상으로 한다.
• 각 간선은 음의 가중치가 없어야한다.  * 왜 존재하면 안되는지 글의 끝에 설명하겠다. 현실세계라고 생각하자.
• 출발지와 도착지를 설정한다.  * 경로를 정하려면, 출발지와 목적지는 있어야된다.
• 이미 방문을 했던 노드로는 방문하지 않는다.
• 다음 노드를 방문할 때는, 최단거리에 있는 노드를 먼저 방문한다.

다익스트라 최단경로

 

다익스트라 최단경로는 출발지에서 노드를 방문하면서, 해당 노드에서 각각의 노드까지의 최단거리를 갱신하는 알고리즘이다.  말로만 들으면, " 이 뭔솔 (이게 무슨 소리야 몰?루)" 이 될 수 있다. 따라서, 다익스트라 알고리즘의 Flow를 잘 이해하자.

 

아래와 같은 그래프 관계가 있고, 각 노드에서 거리를 기록할 배열과, 방문을 기록할 배열을 선언해줬다. 출발점은 1이다.

 

Flow 1

• 가중치를 아래의 그림과 같이 정의하고, 1번 노드부터 출발을 한다.
• 1번 노드에서 방문이 가능한 노드는 2,6,3 번 노드가 있고, 각각의 노드까지의 거리를 기록한다.
• 1번 노드에는 방문을 해주었고, 2,3,6번 노드까지 현재까지 최단거리는 3,8,4가 되었다.

 

Flow 2

• 다음 방문 노드는 Distance 배열 중에서, 가장 작은 값(최단거리)에 있는 노드를 먼저 방문한다.
• 3번 노드를 방문하는 과정을 한번 보자. 우리는 2번 노드에 이미, 1번노드에서 2번노드 까지의 최단거리가 저장되어 있고 , 3번 노드에도 이미 값이 있다.  이 말은 , 즉 1->2->3 or 1->3 중 최단거리가 뭐냐를 정해줘야할 타이밍이 왔다는 거다. 이 부분에서 다익스트라님의 핵심 생각이 드러난다. distance[2]+ 2 to 3 edge 와 distance[3]의 값을 비교해서, 작은값으로 갱신시켜준다
• distance 배열에, 출발지로부터 각각의 노드마다 , 최단거리를 갖고있고, 각각의 노드를 방문하면서, 다시 최단거리를 갱신시키는 방법이라는 말이 이해가 될것이다!

 

 

Flow 3

• 최단거리가 같다면, 뭘 먼저 방문하든 똑같지만, 일반적으로는 작은 번호를 먼저 방문한다.
• 4번 노드를 방문해서, 위와 마찬가지로 최단거리를 갱신시켜준다.
• 5는 INF였기 때문에, distance[4] + edge의 값으로 갱신이 되고,  distance[6]= 4 은 distance[4] +edge =4+5의 값보다 작기 때문에, 갱신이 되지 않는다. 

 

Flow 3

• 이제 6번을 방문해준다.
• 6번은 4번과 5번을 방문할 수 있기 때문에, 위처럼 과정을 반복해준다.
• flow 3,4는 그림만 보고 다익스트라 알고리즘이 이해가 됬는지 보자.

 

 

Flow 4

 

5번 노드는, 방문을 해도되고, 안해도된다. 방문해봤자 , 의미가 없다. (갈 수 있는 노드가 없다)

s

Code

# Direction Graph 라고 가정.
# Not zero-base
# O(N^2), 약 노드 5,000개 이하 정도라면 문제 해결가능 
import sys
input= sys.stdin.readline

N,E=map(int,input().split())
INF=int(1e9)
start=int(input().rstrip())
#인접 리스트
graph=[[] for _ in range(N+1)]
#방문 테이블 
visited=[False for _ in range(N+1)]
# 거리 table 
dist=[INF for _ in range(N+1)]

#그래프(인접 리스트 생성)
for _ in range(E):
    a,b,c=map(int,input().split())
    graph[a].append((b,c))

#방문 하지 않은 노드 중, 가장 짧은 거리에 있는 노드 선택
def get_nearest_node():
    min_value=INF
    index=0
    for i in range(1,N+1):
        if not visited[i] and dist[i]<min_value:
            min_value=dist[i]
            index=i
    return index

def dijkstra(start):
    dist[start] =0
    visited[start] = True
    #출발 노드에서 도달 할 수 있는 노드들 
    for nxt,d in graph[start]:
        dist[nxt] = d
    for i in range(N-1):
        now = get_nearest_node()
        visited[now] = True
        # 현재 노드를 거쳐서, 해당 노드로 가는게 더 작을 경우
        for nxt,d in graph[now]:
            cost=dist[now] + d
            if cost< dist[nxt]:
                dist[nxt]=cost

dijkstra(start)

# 출력
for i in range(1,N+1):
    if dist[i] == INF:
        print("INF!!")
    else:
        print(dist[i])

 

여기서, 우리의 컴퓨터 장인들은 방문하는 순서를 선형적으로 탐색하지 않고, 우선순위 큐라는 자료를 가지고 , 

자동적으로 짧은 거리에 있는걸 방문하게끔 개선을 시켰다.

 

* 개선된 코드 

import sys
#ElogV
import heapq

input= sys.stdin.readline

N,E= map(int,input().split())
INF=int(1e9)
start =int(input().rstrip())
graph=[[] for _ in range(N+1)]
dist=[INF for _ in range(N+1)]

for _ in range(E):
    a,b,c=map(int,input().split())
    graph[a].append((b,c))
    
def dijkstra(start):
    hq=[]
    heapq.heappush(hq,(0,start))
    dist[start] = 0
    while hq:
        distance,now = heapq.heappop(hq)
        if dist[now]<distance:
            continue
        for i in graph[now]:
            cost=distance +i[1]
            if cost<distance[i[0]]:
                distance[i[0]]=cost
                heapq.heappush(hq,(cost,i[0]))

 

Refer

 

나동빈님의 최단경로 알고리즘 강의