[Programming] Dijkstra's Shortest Path Algorithm Concept

Dijkstra's Shortest Path Algorithm Concept

---

포스트 난이도: HOO_Middle

[Notice] 포스트 난이도에 대한 설명

---

 

# Dijkstra's Shortest Path Algorithm Concept

Dijkstra algorithm 또는 Dijkstra's shortest path algorithm이라고 불리는 알고리즘은 최단 거리를 구하는데 많이 사용되는 알고리즘이다. 데이크스트라라는 사람이 개발하고 1950년대에 발표한 알고리즘으로써 오래된 알고리즘이지만 현재 인공지능 분야에서도 활용될 정도로 대표적이고 중요한 알고리즘 중 하나이다. Shortest path algorithm이라고 불리듯이 최단거리를 구하는데 활용하기 좋은 알고리즘이며, 우리가 매일같이 사용하는 내비게이션, 대중교통 찾기 등에 실제로도 활용하고 있다. 물론 Dijstra algorithm은 최단 거리만 찾기 때문에 우리가 실제로 사용하는 내비게이션이나 길 찾기에 들어가는 알고리즘은 Dijstra algorithm을 기반으로 하되, 조건을 추가한 응용된 여러 알고리즘이 포함되어 있다고 생각하면 된다.

# Dijstra algorithm는 O(E+V*logV)

조금 머리 아픈 이야기를 슬슬 시작하자면, Dijstra algorithm의 초창기 버전의 경우 Prioity Queue를 사용하지 않기 때문에 Vertics * Vertics = Vertics^2가 Time Complexity이었다. (O(V^2)). Time complexity를 간단히 가져가려고 노력했고 1980년대에 응용된 Dijstra algorithm이 발표되었다. Fredman and Tarjan 1984 덕분이라고 한다. 이것보다도 우리가 기억해야할 부분은 피보나치 힙을 활용하여 O(V^2)에서 O(E+V*logV)로 바뀌었다는 점이다. 따라서 Upper bound 기준 또는 최악 시간 복잡도 기준에서 Dijstra algorithm는 O(E+V*logV)라는 점을 이해하면 된다.

#Dijstra algorithm의 원리

Dijstra algorithm에 대한 원리는 예제를 통해 살펴보는 것이 이해하기 쉽다. 예제는 필자의 Dijstra algorithm 예제 관련 포스트가 포스팅되어 있으니 참고하길 바란다.

우선 간단하게 말로 이야기를 해보자면 Dijstra algorithm의 원리는 시작 지점에서부터 최단 거리를 하나씩 찾는 것이다. Dijstra algorithm에 연결된 edges들을 확인하여 다음 nodes 또는 vertics까지의 최소 거리를 살펴본다. 최소 거리의 다음 node 또는 vertics까지의 거리를 확인하고 다음 최소 거리 값에 해당하는 edge를 찾아 연결해나가는 방식이 바로 Dijstra algorithm의 주요 원리이다.

여기서 중요한 점은 아직 확인이 되지 않은 거리값은 미지수로 표시한다. 미지수는 우리가 모르는 수이기 때문에 infinity로 표기해준다. 발견된 node 또는 vertics의 값은 infinity 표시를 지우고 위에 시작 지점부터 해당 node 또는 vertics까지의 거리 값을 표시해준다.

마지막으로 중요한 점은 기존 표시된 거리값보다 작은 값이 발견되면 기존 값을 지우고 더 작은 값을 표시해준다. 한마디로 시작 지점부터 최종 목적지까지 더 짧은 최단 거리가 발견되면 해당 Path로 바꾸어 준다는 것이다.

어렵게 들릴 수도 있지만 결과적으로 모든 edges를 비교하여 최단 거리로 최종 목적지를 가는 걸 구하는 방식이 바로 Dijstra algorithm이다.

Dijstra algorithm의 또 다른 포스트를 살펴보면 예제를 올려두었으니 참고하길 바란다.

 

# 인공지능 균일비용 탐색

Dijstra algorithm의 중요한 점은 인공지능 균일 비용 탐색 알고리즘에서 활용된다는 것이다. 균일 비용 탐색에서는 노드 간의 거리를 비교하여 최종 지식 노드를 가는데 들어가는 최소 비용을 찾아야 한다. 따라서 Dijstra algorithm의 최단 거리 알고리즘은 인공지능 균일 비용 탐색 알고리즘에 활용하기 적합하다. 이 부분에 대한 점도 추가 포스트가 필요하다면 필자에게 꼭 알려주길 바란다.

 

---

# In conclusion, 3줄 요약

1. Dijstra algorithm은 최단 거리를 구하는 알고리즘을 많이 활용된다.

2. Dijstra algorithm은 O(E+V*logV)이다.

3. Dijstra algorithm는 인공지능 균일비용 탐색 알고리즘에 활용된다.

---