1. 개념 설명 (1) 다익스트라는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. ( 이것을 줄여서 최단 경로 알고리즘이라고 부른다. ) (2) 다익스트라는 그래프 방향의 유무는 상관없으나, 간선들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다. (3) 만약 음의 가중치를 가지는 간선이 있으며 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용한다. ( 또한 그래프 내에 가중치 합이 음인 사이클이 존재한다면, 무한히 음의 사이클을 도는 경우 합이 음수 무한대로 발산하기 때문에 최단 경로를 구성할 수 없다. ) 2. 과정 - 실제로 수행되는 과정이며, 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 기록하고 있다. 3. 입출력 조건 ..