다익스트라 알고리즘

다익스트라(Dijkstra) ?

• 다익스트라 알고리즘은 그래프에서 한 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘 중 하나이다.
• 해당 노드까지의 최단 경로를 찾는 과정에서 다른 모든 정점까지의 경로값도 계산해주면서 각 정점까지의 최단 경로도 모두 찾게 된다 !
• 가중치가 양수일 때만 사용 가능하다 !

💡 다익스트라 핵심 개념 - Greedy

• 다익스트라는 그리디(Greedy) 알고리즘의 일종으로, 매 단계마다 **가장 최적의 선택(현재 최단 거리를 가진 정점)**을 한다. → 즉, 아직 방문하지 않은 정점 중에서 최단 거리의 정점을 선택해 탐색한다.

<aside> 💡

방문 여부도 체크해야 하나 ?

• 따로 체크할 필요가 없다 ! → 노드는 한 번 방문했을 때 최단 거리값으로 갱신되기 때문에, 아래처럼 거리를 갱신하는 조건문에 걸리지 않아 우선순위 큐에 이후 방문할 노드로 추가될 일이 없다 !

if (newDist < distances[neighbor]) {
		distances[neighbor] = newDist;
		pq.add(new Edge(neighbor, newDist));
}

</aside>

💡 다익스트라 핵심 개념 - 최단 거리 테이블

• 다익스트라 알고리즘의 최단거리 테이블은 특정 시작 정점에서 모든 다른 정점까지의 최단 거리를 기록하는 테이블이다. → 다익스트라 알고리즘이 실행되는 동안 최단 거리를 점진적으로 갱신하면서 경로를 탐색할 때 사용된다.

최단 거리 테이블의 구성과 갱신 과정

1. 초기화

   1. 시작 정점에서의 거리는 0으로 설정한다.
   2. 나머지 모든 정점은 아직 방문되지 않았으므로 거리를 무한대(∞; INF)로 설정한다.

2. 탐색 과정

   1. 현재 테이블에 있는 최단 거리가 가장 작은 정점을 선택하여 해당 정점을 방문 처리한다.
   2. 선택된 정점을 기준으로 인접한 정점들을 확인하며, 최단 거리 테이블을 갱신한다.
   3. 이 과정을 모든 정점을 방문할 때까지 반복한다.

3. 결과

   1. 시작 정점에서 모든 정점까지의 최단 거리를 나타내게 된다.