Dijkstra Algorithm

#Algorithm #Algorithm_Dijkstra #DataStructure-Heap #DataStructure-Priority_Queue

1. Dijkstra

=> 출발점에서 도착지점(or anywhere)까지 연결되는 경로의 최소 혹은 최대 비용을 구하는 문제에 사용할 수 있는 알고리즘

(+다익스트라는 이 알고리즘을 만든 사람의 이름이다.)

다익스트라(Dijkstra) 알고리즘, 한은기 이 포스트에 그림 설명으로 탐색 방법이 잘 나와 있다. 이해하는데에 도움이 많이 되었다.

1-1. 키워드

그래프

다익스트라 알고리즘은 그래프에 적용된다. 유향그래프, 무향그래프 모두에 사용할 수 있다.

출발 노드

출발 노드와 연결된 노드 중에서 엣지의 비용에 따라 다음 경로가 결정되는 특성상 최초 출발 노드가 어디인지가 중요해진다.

도착 노드

출발 노드와는 다르게 도착노드는 정해져 있다면 로직에서 필터하여 전체 노드를 탐색하지 않아도 되게 한다는 점에서 의의가 있지만, 그렇지 않고 전체 탐색을 하여야 하는 경우에도 다익스트라 알고리즘이 사용된다.

우선순위 큐

다익스트라 알고리즘에서 가장 중요한 부분이라고 할 수 있다. 엣지의 비용이 가장 적은 혹은 가장 큰 부분을 선택하여 계산해 나갈 때에만 최종 경로에 도달했을 때 우리가 원하는 결과를 얻을 수 있다. 때문에 경로 탐색을 위한 노드 추가 시 우선순위 큐를 이용하여 정렬한다.

2. 개인적인 이해 및 한계

왜 큐에 있는 노드들 중에서 비용이 가장 작거나 큰(이하 조건에 맞는.) 엣지로 연결된 노드를 다음 방문 노드로 선택하여야 하는지에 대한 명확한 증명을 하지 못한 느낌이다.
선택된 노드에 다시 연결된 노드의 가중치 계산에 영향을 미치기 때문에 비용의 조건에 맞는 최대 혹은 최소값을 선택하여 진행하게 될 거라는 예상만이 될 뿐이다.

추가적으로 경로탐색이 아닌 총 경로의 가중치를 측정하는 알고리즘이라는 것에 유의해야 할 것 같았다. 나에게 '경로 탐색'은 연결-연결된 경로 리스트의 나열이라는 의미인데, 다익스트라는 경로의 탐색을 순차적이거나 인접행렬끼리 하지 않기 때문이다. BFS와 비슷한 방식으로 노드를 추가하지만 우선순위큐를 사용하기 때문에 BFS처럼 인접 노드로 바로 이동하는 것이 아닌 가중치 계산을 염두해 둔 경로 이동이 되기 때문에 계산 중에는 경로가 튈 수 있다.

0. 관련 문제