Chapter 09 : 최단 경로

:가장 짧은 경로를 찾는 알고리즘

다익스트라 알고리즘

• 특정한 노드에서 출발하여 다른 노드로 가는 최단 경로를 구함
• 음의 간선이 없을 때 정상적으로 동작
• 그리디 알고리즘
• 각 노드에 대한 현재까지의 최단거리 정보를 1차원 리스트에 저장하며 리스트를 갱신

1. 간단한 다익스트라
   접근하지 않은 노드 중 가장 최단 거리가 짧은 노드를 순회 탐색함
   시간 복잡고 O(V^2(

2. 우선순위 큐를 사용하는 다익스트라
   우선순위 큐 - PriorityQueue/heapq사용
   , 파이썬 라이브러리에선 최소 힙 구조 이용(값이 낮은 데이터가 먼저 삭제)

플로이드 워셜 알고리즘

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용
• 시간 복잡도 O(N^2)
• 다이나믹 프로그래밍
• 2차원 리스트에 최단 거리 정보 저장