📌 최단 경로 문제
- 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미함
- 다양한 문제 상황
- 한 지점에서 다른 한 지점까지의 최단 경로
- 한 지점에서 다른 모든 지점까지의 최단 경로
- 모든 지점에서 다른 모든 지점까지의 최단 경로
- 각 지점은 그래프에서 노드로 표현
- 지점 간 연결된 도로는 그래프에서 간선으로 표현
📌 다익스트라 최단 경로 알고리즘 개요
- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다
- 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다
- 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않습니다
- 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다
- 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다
다익스트라 동작과정
[초기 상태] 그래프를 준비하고 출발 노드를 설정한다
-
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 1번 노드를 처리한다
-
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 4번 노드를 처리한다
-
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 2번 노드를 처리한다
-
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 5번 노드를 처리한다
-
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 3번 노드를 처리한다
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 6번 노드를 처리한다
✅ 다익스트라 알고리즘의 특징
- 그리디 알고리즘: 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다
- 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다
- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다
- 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장된다
Reference
꿈꿈