목록최단경로 구하기 (1)

YJ_Scribbles

Dijkstra(다익스크라)최단경로 알고리즘(그리디 알고리즘)

★ 최단 경로(Shortest Path) 문제 - 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제 ☆ 최단 경로를 찾는 가장 대표적인 알고리즘 - 다익스트라(Dijkstra) 최단 경로 알고리즘 ☆ 다익스트라 알고리즘 - 주어진 출발점에서 시작 - 출발점으로부터 최단 거리가 확정되니 않는 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정 ★ Dijkstra(다익스트라) 알고리즘 ShortestPath(G, s) 입력: 가중치 그래프 G=(V,E), |V|=n , |E|=m 출력: 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D 1. 배열D를 ∞로 초기화시킨다. 단, D[s]=0으로 초기화한다. // 배열 D[..
이론_전공/알고리즘 2020. 11. 1. 21:30
이전 Prev 1 Next 다음