최단 경로란? 가장 짧은 거리를 찾는 알고리즘 그래프가 주어졌을 때 특정 노드에서 다른 노드까지의 최단 거리를 구할 때 사용 경로 계산 방식에는 3가지 종류가 존재 1. One-To-One : 한 지점에서 다른 특정 지점까지의 최단경로 2. One-To-All : 한 지점에서 다른 모든 지점까지의 최단경로 3. All -To -All : 모든 지점에서 모든 지점까지의 최단경로 다익스트라 알고리즘 - 위의 경로 계산 방식 중 2번째 One-To-All의 대표적인 방법 - 음의 간선이 없을 때 정상적으로 작동 - 매 상황에서 가장 비용이 적은 노드를 선택(그리디 알고리즘으로 분류) 동작 과정 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단거리 노드 선택 4. 해당 노..