[알고리즘] 다익스트라(Dijkstra) 알고리즘 1. 다익스트라(Dijkstra) 알고리즘이란? - 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 - 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. > 모든 정점을 방문하되, 최단 경로로! - "최단 거리는 여러 개의 최단 거리로 이루어져있다."는 다이나믹 프로그래밍의 특성 반영 > 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리를 그대로 사용 - 가중치가 양수일 때만 사용 가능하다 2. 알고리즘의 동작 단계 (1) 출발 노드, 도착 노드 설정 (2) 출발 노드를 기준으로 각 노드의 최소 비용 저장 (3) 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택 (4) 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 > 간선 비용.. 이전 1 다음
