[Algorithm] 다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘이란?

• 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘
• 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알 수 있음
• 다만 이때 음의 간선을 포함할 수 없는데(비용이 음수일 수 없음!) 현실에선 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 적합하다고 할 수 있다.
• 다이나믹 프로그래밍인 이유는 '최단 거리는 여러 개의 최단 거리로 이루어져있기 때문'. 즉, 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 사용하게 된다.

알고리즘

1. 출발 노드를 설정
2. 출발 노드를 기준으로 각 노드까지 가는 비용을 최소 비용으로 저장하고 출발 노드를 방문한 노드로 체크
3. 현재 방문한 노드들과 연결되어 있고 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택 후 해당 노드를 방문한 노드로 체크
4. 선택된 노드를 거쳐서 특정한 노드로 가는 경우를 고려해서 최소 비용 갱신
5. 3-4번 반복

방식은 다른 블로그에 잘 나와 있다.

https://blog.naver.com/ndb796/221234424646

시간 복잡도

• 일반적으로 선형 탐색으로 찾게 되면 O(N^2)가 걸림
  • 전체 (N - 1)번 탐색 x (최소비용이 드는 노드 찾기 = N번)
• 우선순위 큐와 인접리스트 방식을 이용하면 O(E*logN)(E=간선의수, N=정점의수)으로 해결할 수 있음
  • 최소힙으로 추출 O(logN) x 모든 간선 확인 O(E)

 

 

Reference

https://blog.naver.com/ndb796/221234424646