카테고리 없음
[알고리즘] 그리디
다익스트라 (Dijkstra's Algorithm)다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 그리디 알고리즘이다. 이 알고리즘은 항상 현재 상태에서 가장 비용이 적은 노드를 선택하는 방식으로 동작한다.시작 노드를 설정하고, 시작 노드에서 직접 연결된 모든 노드까지의 거리를 초기화한다.미방문 노드 중에서 현재까지의 최단 거리가 가장 짧은 노드를 선택한다.선택한 노드를 방문 처리하고, 이 노드를 거쳐 갈 수 있는 다른 노드들의 최단 거리를 갱신한다.모든 노드를 방문할 때까지 2-3 과정을 반복한다. 구현 상세:touch[i]: 노드 i로 가는 최단 경로에서 i 직전에 방문하는 노드 번호length[i]: 시작 노드(v₁)에서 노드 i까지의 현재까지 ..
