다익스트라

다익스트라는 그래프의 어떤 정점 하나를 시작점으로 선택하고 나머지 정점들로의 최단거리를 모두 구하는 것이다. (시작점에서 다른 모든 정점으로의 최단 경로)
정점 개수가 V, 간선 개수가 E일 때 O(ElogV)의 시간 복잡도를 갖는다.
여기서 O(ElogV)는 인접 리스트로 구현했을 때 해당하고, 인접 행렬로 구현했을 경우에는 O(V^2)이 된다.
그래프는 무향이거나 유향인데 대체로 유향인 경우가 많다. 또한 모든 거리값이 음수가 아닐 때만 사용할 수 있다. 이 이동 거리가 거리 대신 비용(cost)라는 용어로 대체되고 최소 비용을 구하라고 할 수도 있다.

다익스트라 알고리즘은 다음과 같이 작동한다.

1. 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하나 선택해 방문한다.
2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다.