최단경로 알고리즘(1)/ 다익스트라 최단경로

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 

코드 출처: https://github.com/ndb796/python-for-coding-test

---

▶ 최단경로 알고리즘이란?

최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘으로 한 지점에서 다른 지점, 모든 지점에서 다른 모든 지점까지의 최단 경로 등을 구하는 등 여러 유형의 문제가 있다. 각 지점은 노드로 표현되고 지점 간 연결된 선은 간선으로 표현한다. 

 

 

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

특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 계산한다. 현실세계의 간선은 음의 부호를 가진 간선으로 표현되지 않기 때문에 이러한 음의 간선이 없을 때 정상적으로 작동한다. 해당 알고리즘은 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다는 점에서 그리디 알고리즘으로 분류되기도한다.

 

▷ 단계

1) 출발 노드를 설정한다

2) 최단 거리 테이블을 무한으로 초기화한다, 

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

4) 최단 거리 테이블에 각 노드에 대한 현재까지의 최단거리 비용을 기록하는데, 이 과정에서 나중에 기존에 기록되어 있는 것보다 더 짧은 경로를 찾으면 해당 테이블을 더 짧은 경로의 비용으로 갱신한다.

5) 3),4)을 반복한다. 

 

▷ 예시

다음 그래프를 통해 1번에서 다른 모든 노드까지의 최단거리를 다익스트라 최단경로 알고리즘으로 생각해보자. 

> 1번이 출발노드로 0으로 초기화 한다

> 다른 노드들은 모두 무한으로 초기화 한다 -> [0, inf, inf, inf, inf, inf]

> 1에서 출발하는 노드는 2,5,4가 있는데 경로 길이가 2인 2와 4중에서 노드 숫자가 더 작은 2를 먼저 선택한다. 2로 갈 수 있는 최단 경로는 2이다. -> [0, 2, inf, 2, 5]

> 2에서는 3으로만 갈 수 있다. 1에서 3까지 갈수있는 최단경로는 2+3으로 5이다. -> [0,2,5,2,5]

> 이번에는 1에서 4로 이동한다. 4에서 갈 수 있는 노드는 3과 5이다. 1번에서 4번을 거친 3번까지는 2+4=6으로 갈 수 있는데 현재 3번 노드에 저장돼있는 최단경로 5가 더 작으므로 갱신하지 않는다. 1번에서 5번까지는 2+4=6인데 마찬가지로 최단 경로 5가 더 작으므로 갱신하지 않는다. -> [0,2,5,2,5]

> 이번에는 3번 노드가 선택된다. 3번 노드에서 갈 수 있는 노드는 4번과 5번이다. 1번에서 3번을 거쳐 4번으로 가는 경로는 5+4= 9이므로 갱신하지 않는다. 1번에서 5번으로 가는 경로는 5+2=7로 역시 갱신하지 않는다. 

> 방문하지 않은 노드는 5번 노드만 남았지만 이미 나머지 4개의 노드에 대한 최단거리가 확정된 상태이므로 더이상 테이블을 갱신할 필요가 없기에 알고리즘이 종료된다. 

> 따라서 1번에서 모든 노드로의 최단 거리는 [0,2,5,2,5]로 나타낼 수 있다. 

 

▷ 구현

다익스트라를 구현하기 위해 간단한 방법으로 구현하는 방법도 있다. 

우선 데이터를 입력받고 초기값들을 설정해주는 코드이다. 

 

입력 받은 노드 정보와 간선정보 등을 통해 다익스트라 알고리즘을 구현하는 코드이다. 

 

이 방법의 경우 시간복잡도가 O(V^2)이기 때문에 노드와 간선의 개수가 많을 때 적합하지 않다.

 

따라서 개선된 다익스트라 알고리즘을 구현할 수 있어야 한다. 개선된 알고리즘은 코드는 복잡하지만 최악의 경우에도 O(ElogV)의 시간복잡도를 가진다. 해당 알고리즘 구현은 다음 포스팅에 정리하였다.