최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미. 1. 다양한 문제 상황 1) 한 지점에서 다른 한 지점까지의 최단경로 2) 한 지점에서 다른 모든 지점까지의 최단경로 3) 모든 지점에서 다른 모든 지점까지의 최단경로 - 각 지점은 그래프에서 노드로 표현. - 지점 간 연결된 도로는 그래프에서 간선으로 표현. 2. 알고리즘 동작 과정 1. 출발 노드를 설정. 2. 최단거리 테이블을 초기화. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 (weight)를 선택. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다. But! 총 O(V)번에 걸쳐서 최단거리가 가장 짧은 노드를 매법 선형 탐색해야 한다. 따라서 전체 시간 복잡도는 O(V2) 이다...