Dijkstra 알고리즘에 관하여
최단 거리를 빠르게 계산해주는 알고리즘이다. Negative cycle이 없어야만 정당하게 돌아간다. 일반적으로 모든 간선의 거리가 0 이상일 때 사용한다. 시작 정점에서부터 임의의 정점까지 도달하는데 필요한 거리 배열을 구한다. 처음 배웠을 때 굉장히 어려웠던 알고리즘으로 기억한다. 알고리즘이 작동하는 방식보다도 수학적인 매커니즘이나 직관을 잡는데 시간이 오래 걸렸다. 개인적으로 탐욕법과 관련된 모든 것들이 처음 습득하기가 다 어려운 것 같다.. 확실히 응용 문제를 많이 다루면서 개념이 점점 잡힌다. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는..
