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

가장 빠른길 찾기 ?

한 지점에서 다른 특정 지점까지의 최단경로를 구해야 하는 경우를 뜻한다.

크게 세가지가 있다.

 

1) 다익스트라 알고리즘

2) 벨만 포드 알고리즘

3) 플로이드 워셜 알고리즘

 

가장 중요한 것은 다익스트라 알고리즘과 플로이드 워샬 알고리즘이다. 두가지만 파악을 해도 코딩테스트 수준에서

최단경로 문제는 어렵지 않게 해결 할 수 있다.

 

1. 다익스트라 알고리즘

GPS 소프트웨어의 가장 기초적 알고리즘으로 채택된다. 다익스트라 알고리즘은 그리디 알고리즘을 사용한다고 생각하면 된다.

매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다.

여기서 또 필요한 알고리즘은 Priority Queue 우선순위 큐이다. 가장 작은 간선의 수를 먼저 실행시켜야 하기 때문이다.

 

< 원리 >

1) 출발 노드 설정

2) 최단 거리 테이블을 초기화

3) 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다.

4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다.

5) 위 과정에서 3, 4를 반복한다.

 

다익스트라 알고리즘 예제

 

1) 우선 여기서 첫 번째로 출발할 노드를 선택한다. ( 출발 노드는 1)

2) 최단거리테이블을 초기화 한다. ( 모두 INF : 큰 숫자로 초기화 한다.)

1	2	3	4	5	6
0	INF	INF	INF	INF	INF

3) 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다.

1에서 4를 가기위한 거리는 1

1에서 2를 가기위한 거리는 2

1에서 3을 가기위한 거리는 5

그리고 PriortyQueue에 넣어준다

현재 PriorityQueue = [[1, 1, 4], [2,1,2], [5,1,3]] 

1	2	3	4	5	6
0	2	5	1	INF	INF

 

4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다.

PriorityQueue.get() 해주면 [1,1,4]

 

4에서 출발하는 노드를 탐색

4에서 1을 가기위한 거리는 1 : 1 -> 4 -> 1는 2이므로 0보다 크다, PriorityQueue에 넣어주지 않음

4에서 2를 가기위한 거리는 2 : 1 -> 4 -> 2는 3이므로 2보다 크다, PriorityQueue에 넣어주지 않음

4에서 3을 가기위한 거리는 3 : 1 -> 4 -> 3은 4이므로 5보다 작다 PriorityQueue에 넣어줌

PriorityQueue = [ [2,1,2], [4,1,3], [5,1,3]] 

1	2	3	4	5	6
0	2	4	1	INF	INF

 

< 3-4 반복 >

PriorityQueue.get() 해주면 [2,1,2]

2에서 1을 가기 위한 거리는 2 : 1 -> 2 -> 1 : PriorityQueue에 넣어주지 않음

2에서 4를 가기 위한 거리는 4 : 1 -> 2 -> 4: 1보다크다 PriorityQueue에 넣어주지 않음

2에서 3을 가기 위한 거리는 3 : 1 -> 3 -> 4 : PriorityQueue에 넣어주지 않음

현재 PriorityQueue = [[4,1,3], [5,1,3]] 

1	2	3	4	5	6
0	2	4	1	INF	INF

 

이런식으로 3과 4를 반복한다.

 

Python 소스코드

---

from queue import PriorityQueue

N = 6 # 노드의 개수

weights = [
    [1,2,2],
    [1,4,1],
    [1,3,5],
    [2,4,2],
    [2,3,3],
    [4,3,3],
    [4,5,1],
    [5,3,1],
    [5,6,2],
    [3,6,5]
] # [1,2,2]는 1에서 2로가는 간선의 크기 : 2

graph = [[9999 for _ in range(N)] for _ in range(N)]
for i in weights:
    graph[i[0]-1][i[1]-1] = i[2]
    graph[i[1]-1][i[0]-1] = i[2]

for i in range(N):
    graph[i][i] = 0
    graph[i][i] = 0

visited = [False for _ in range(N)] # 방문한 노드를 확인 하기 위한 visited
weight = [9999 for _ in range(N)]

def dkstra(K):
    weight[K] = 0
    queue = PriorityQueue()
    visited[K] = True

    for i, value in enumerate(graph[K]):
        if weight[K] + value < weight[i]:
            weight[i] = weight[K] + value
            queue.put([weight[i], K, i])
    
    
    while queue.qsize() != 0:
        values = queue.get() # [1,0,3]

        for i, value in enumerate(graph[values[2]]): # 1 2 3 0 1 9999
            if visited[i] == True:
                continue
            if weight[values[2]] + value < weight[i]:
                weight[i] = weight[values[2]] + value
                queue.put([weight[i], values[1], i])
                visited[i] = True

    return


dkstra(0) # 시작 노드는 1이므로 0을 넣어준다, list는 0부터 시작 하므로, 
print(weight) # [0, 2, 4, 1, 2, 4]

사용 알고리즘 : 그리디 알고리즘, priority queue

priorityqueue 자체에 그리디알고리즘이 적용돼있다고 생각하면 된다,

방문하지 않은 노드중에 가장 거리의 weight가 낮은 곳을 넣어주는 형식으로 진행이 된다.

 

시간 복잡도는 O(ElogV)로 V = 노드의개수 E는 E개의 원소의 개수라고 생각하면된다.