다익스트라
- 최단경로 탐색 알고리즘
- 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이때 음의 간선을 포함할 수 없다.
- 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 매우 적합한 알고리즘
- 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다.
현재에서 가장 짧은 경로인 2에서 시작한다.
- 나중에 컴퓨터에서 1->3의 비용이 6인데 반해 경로 1-2-3이 총 4로 더 저렴하다는 것을 알게된다.
- 현재 까지 알고 있던 최단 경로를 계속해서 갱신
작동 과정
- 출발 노드를 설정
- 출발 노드를 기준으로 각 노드의 최소 비용을 저장
- 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택
- 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용 갱신
- 위 과정에서 3번~4번 반복
안녕하세요