heap (1) 썸네일형 리스트형 [알고리즘]다익스트라 최단 경로 알고리즘 개념 부수기 / heap이 뭐야? 다익스트라 최단 경로 알고리즘 정점 한개를 기준으로(=시작 정점) 다른 모든 정점을 도착하는 단일점에서의 최단 경로 알고리즘 방향 그래프, 무방향 그래프 모두 적용 간선의 가중치가 음수면 다익스트라 알고리즘을 사용할 수 없다. 가장 가까운 정점(방문x 정점)을 선택해 추가할 때, 추가된 새로운 정점에 의해 단축되는 경로가 있다면 해당 경로로 최단 경로를 수정하는 알고리즘이다. 집합 또는 vertex방문체크를 하면서 최단 경로를 구할 경우( 원래의 알고리즘 ) 시간복잡도는 O(E + V^2) == O(V^2)이다. 우선순위 큐를 활용할 경우 시간 복잡도는 O(ElogV)이다. Algorithm 1. set distance 2.시작 정점 방문 체크 3. 방문하지 않은 정점 중 시작점과 최소거리인 정점을 찾아.. 이전 1 다음
