DevKim

- '하나'의 정점에서 다른 모든 정점으로 가는 최단 경로 [ 조건 ] - 음의 간선이 존재하지 않음 [ 기존의 선형탐색 방법의 다익스트라 ] - O(n^2) 의 시간 복잡도를 가짐 - 문제점은 노드의 개수가 10,000개가 넘어가는 문제라면 시간초과 가능성이 높음 [ 우선순위 큐를 이용한 다익스트라 ] - 힙을 이용하여 구현 - python 에선 heapq 라이브러리로 구현되어있음 - O(NongN) 의 시간복잡도 [ 과정 ] 최단거리 테이블을 초기화(자기 자신은 0, 직접 연결되어있지 않는건 무한대로 초기화) 처음엔 가장 가중치가 작은 값을 선택함 하나의 노드를 선택하고 해당 노드를 거쳐서 가는 경우를 모두 고려하여 가장 최소인 값으로 업데이트 (이때, 값이 새로 갱신된 경..