다익스트라(Dijkstra) 알고리즘은 가장 유명한 그래프 알고리즘 중 하나이다. 다익스트라 알고리즘은 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산한다.

다익스트라 알고리즘은 BFS와 비슷하게 탐색하는데 정점간에 연결된 간선에 가중치가 있다면 BFS로는 정확한 답을 구하기가 어렵다. BFS는 오로지 정점들을 방문할 뿐이며, 더 낮은 가중치로 방문하는 경우를 판단하지않기때문이다.

BFS에서는 큐나 우선순위 큐를 사용하여 큐에 정점의 번호만 넣어 사용하는데, 다익스트라 알고리즘은 우선순위 큐에 정점 번호와 해당 정점까지의 최단 거리를 쌍으로 넣어준다. 이로써 아직 방문하지 않은 정점까지 최단 거리를 구하는 과정이 간단해진다.

각 정점까지의 최단 거리를 저장하는 배열 dist[]가 있고, 각 정점을 방문할 때 마다 인접한 정점을 모두 검사(방문x)한다. 간선 (u, v)를 검사했는데 v가 아직 방문하지않는 정점이라고 했을 때, u까지의 최단 거리(dist[u])에 간선 (u, v)의 가중치를 더해 경로의 길이를 계산한다. 만약 최단 거리라면 dist[v]를 갱신하고 큐에 (v, dist[v]) 를 넣는다. 이렇게 큐에 넣고 꺼내고를 반복한다면 즉, 모든 정점을 최단 거리로 방문하게 된다.

s 정점에서 z 정점까지 방문 순서를 도식화했다.

• 방문하지않은 노드는 infinity 또는 -1로 초기화한다.

출처: http://nsyang-textcube.blogspot.kr/2009/06/최단거리알고리즘dijkstra.html