인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

Bellman-Ford 알고리즘

Worst Scenario

Dijkstra 알고리즘

Dijkstra 알고리즘

수도코드

시간 복잡도를 낮추는 방법

• 이진힙을 사용

시간복잡도

• prim의 알고리즘과 동일함

• 우선순위 큐를 사용하지 않고 단순하게 구현할 경우 O(n^2)

• 이진힙을 우선순위 큐로 사용할 경우 O(nlongn + mlogn)

• Fibonacci Heap을 사용하면 O(nlogn+m)에 구현가능