2021.06.30
다익스트라 최단 경로 알고리즘(Dijkstra Shortest Path Algorithm)
다익스트라 최단 경로 알고리즘(Dijkstra Shortest Path Algorithm) 그래프에서 단일 시작(Single Start) 최단 경로 문제(Shortest Path Problem) 구글 지도 또는 자동차 내비게이션 등에서 경로를 탐색할 때 사용됨. 문제 정의 주어진 그래프 G = 의 시작 정점(Source Vertex) 과 목적 정점(Destination Vertex) 이 주어질 때, 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 구하시오. V : 정점의 집합 E : 에지의 집합 각각의 에지는 가중치를 가지고 있음. 다익스트라 알고리즘(Dijkstra's Algorithm) 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘 프림의 MST 알고리즘을 약간 변경한 형태 ..
