dijkstra's algorithm (1) 썸네일형 리스트형 [Algorithm] Dijkstra's Algorithm (다익스트라 알고리즘) 1. Dijkstra's Algorithm 다익스트라 알고리즘은 한 정점으로부터 다른 정점으로의 최단 경로를 찾는 알고리즘이다. 매반복마다 현 시점에서 가장 가까운 정점을 찾아 해당 정점에 인접한 간선들을 통해 경로를 찾아 확장해 나가는 방식이다. 그래프의 방향 유무는 상관없으나 간선이 음수 가중치를 가지는 경우에는 사용할 수 없다. 2. 다익스트라 알고리즘 구현 1) 초기에 출발점으로부터 해당 정점으로의 거리를 저장할 공간과 방문여부를 저장할 공간을 선언한다. 2) 해당 배열에서 출발점은 0, 나머지 정점은 무한대로 초기화한다. 3) 최단 거리를 저장하는 배열에서 미방문 정점 중 가장 거리가 가까운 정점을 선택한다. 4) 해당 정점을 방문한 정점으로 저장한다. 5) 선택된 정점에 간선으로 연결된 인접한.. 이전 1 다음