Dijkstra(다익스트라) (1)

개념

• 다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다.

• 이 과정에서 도착 정점(노드) 뿐만 아닌, 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로를 모두 찾게 된다.

• 매번 최단 경로의 정점을 선택해 탐색을 반복한다.

• 그래프 알고리즘 중 최단 거리, 최소 비용을 구하는 알고리즘은 다익스트라 외에 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다.

특징

1. 출발 노드와 도착 노드를 설정한다.

2. '최단 거리 테이블' 을 초기화한다.

3. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. (선택한 노드는 방문 처리한다.)

4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트 한다.

5. (3) ~ (4) 과정을 반복한다.

과정

1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기

2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기

3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기