최단 경로 알고리즘

최단 경로 알고리즘에 대표적인 알고리즘으로는 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있다.

 

다익스트라 최단 경로 알고리즘 

 

그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

이 때 조건은 음의 간선이 없는 경우에 정상적으로 동작한다는 점이다. 현실 세계에서의 길에는 음의 간선의 표현될 일이 없으므로 실제 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.

 

다익스트라 알고리즘을 그리디 알고리즘(탐욕법)으로도 분류된다. '매번 가장 적은 비용의 노드를 선택'하는 임의의 과정을 반복하기 때문이다.

 

알고리즘은 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단거리를 단계마다 게속 갱신해 나간다. 즉 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다. 

 

다익스트라는 흔히 2가지 알고리즘 방식으로 구현 가능한데 다음과 같다. 각 예시는 아래에서 나타내겠다.

            방법 1. 구현하기 쉽지만 느리게 동작하는 코드

            방법 2. 구현하기 까다롭지만 빠르게 동작하는 코드

 

 

다익스트라 알고리즘의 동작 원리를 간단하게 그림과 표로 나타내보자 !

 

예시로 사용될 그래프

 

초기상태에서는 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화하는데 흔히 사용하는 방법은 지수 표기법을 사용하는 것이다.

le9라고 사용하면 10억을 의미한다. 파이썬에서는 le9를 실수형 자료형으로 처리하기 때문에 int(le9)로 초기화한다.

 

-초기 단계 리스트-

노드 번호	1	2	3	4	5	6
거리	0	무한	무한	무한	무한	무한

 

- step 1- :    1번에 해당하는 간선에 대해서 길 찾기 시작

노드 번호	1	2	3	4	5	6
거리	0	2	5	1	무한	무한

 

-step2- :     방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 => 4번이므로 4번 노드를 거쳐 갈 수 있는 노드를 확인한다.

노드 번호	1	2	3	4	5	6
거리	0	2	1(4) + 3 = 4	1	1(4) + 1 = 2	무한

 

-step3- :     2번 노드 선택 , 2번 노드를 거쳐 갈 수 있는 노드 확인

노드 번호	1	2	3	4	5	6
거리	0	2	4	1	2	무한

 

-step4- :     5번 노드 선택, 5번 노드를 거쳐 갈 수 있는 노드 확인

노드 번호	1	2	3	4	5	6
거리	0	2	2(5) + 1 = 3	1	2	2(5) + 2 = 4

 

-step5- :      3번 노드 선택 , ""

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	무한

 

-step6- :       6번 노드 선택 표는 step5와 같다.

 

 

모든 노드에 탐색이 실행되었을 때 시작 노드로부터 각 노드로 갈 수 있는 최단 경로가 구해지게 된다.

다익스트라 알고리즘에서  " 방문하지 않은 노드 중 최단 거리가 짧은 노드를 선택 " 하는 과정을 반복하는데 

이렇게 선택된 노드는 '최단 거리'가 완전히 선택된 노드로 더이상 알고리즘을 반복해도 최단 거리가 감소하지 않는다. 

 

(ex) step 2에서 4번 노드가 선택되어 4번 노드를 거쳐 이동할 수 있는 경로를 확인하고 그 이후 4번 노드의 최단 거리는 변화 X

따라서 즉," 다익스트라 알고리즘이 진행되면서 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는다. "

 

 

 

간단한 다익스트라 알고리즘

 

알고리즘을 그대로 구현한다면 알고리즘은 O(V^2)의 시간 복잡도를 가진다. ( V: node 갯수 )

 

1. 각 노드에 대한 최단거리를 담을 N개의 1차원 배열을 선언한다.
2. 단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인한다.    (순차탐색)

 

 

간단한 다익스트라 알고리즘 코드.py

# 모든 리스트는 ( 노드의 개수 + 1)의 크기로 할당하여, 노드의 번호를 인덱스로 하여 바로 리스트에 접근하도록 함

 

import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) #노드,간선 수 start = int(input()) #시작 노드 graph = [[] for i in range(n+1)] visited = [False] * (n+1) distance = [INF] * (n+1) for _ in range(m):  # 모든 간선 정보 입력     a,b,c = map(int, input().split())     graph[a].append((b,c)) # 방문하지 않은 노드 중 , 최단 거리가 짧은 노드의 번호 반환 def get_smallest_node():     min_value = INF     index = 0  #최단 거리가 가장 짧은 노드( index )     for i in range(1, n+1):         if distance[i] < min_value and not visited[i]             min_value = distance[i]             index = i         return index def dijkstra(start):     #시작 노드에 대해 초기화     distance[start] = 0     visited[start] = True     for j in graph[start]:         distance[j[0]] = j[1].    #step 1상태 완료     for i in range(n-1):          #단계별 반복 시작         now = get_smallest_node()         visited[now] = True         for j in graph[now]:      #최단거리를 찾을경우 갱신             cost = distance[now] + j[1]             if cost < distance[j[0]]:                 distance[j[0]] = cost ================================ dijkstra(start) for i in range(1, n+1):     if distance[i] == INF:         print("무한")     else:         print(distance[i])

 

시간복잡도가 O(V^2)인 이유는 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색하고, 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문이다.