Dijkstra의 알고리즘


<사업부>
n개의 꼭지점과 m개의 가장자리가 있는 유향 또는 무향 가중 그래프가 주어집니다. 모든 간선의 가중치는 음수가 아닙니다. 일부 시작 정점 s가 지정됩니다. 정점 s에서 다른 모든 정점까지의 최단 경로 길이를 찾고 최단 경로 자체를 인쇄하는 방법도 제공해야 합니다.
 
이 문제를 "단일 소스 최단 경로 문제"라고 합니다. (단일 소스 최단 경로 문제).

1-K BFS와 동일한 작업을 수행하지만 K에 관계없이 수행합니다. 또한 1-K BFS와 마찬가지로 음수 에지를 제대로 처리하지 않습니다.
<사업부>
알고리즘:
Dijkstra의 알고리즘 자체는 N 반복으로 구성됩니다. 다음 반복에서 정점 V  아직 표시되지 않은 꼭짓점 중에서 가장 짧은 거리로 이 꼭짓점이 표시되고 인접 꼭지점의 이완이 발생합니다.
<사업부>

 알고리즘의 최종 점근적 동작: O(n2+ m)

Training problem

다익스트라: 더 비기닝(C++)

Training problem

다익스트라

Dijkstra 알고리즘의 순진한 구현의 점근적 동작은 \(O(n^2 + m)\)이므로 정점 수가 증가함에 따라 작업 속도가 만족스럽지 않게 됩니다.
 개선을 위해 다양한 데이터 구조를 사용할 수 있습니다: 피보나치 힙, 세트 세트 또는 우선 순위 대기열 priority_queue. 
set의 예를 고려하면 최종 점근선은 다음과 같습니다. \(O(n log (m))\) , 세부정보.

Training problem

O(M logN) c 집합의 Dijkstra 알고리즘: 시작(C++)