다익스트라 알고리즘
그래프에서 하나의 노드를 기준으로 전체 노드의 최단거리를 구함1. 처음 0번 노드에 연결된 노드들의 거리를 받음
2. 0번 노드에 연결된 것들 중 최소 거리의 노드를 구함
3. 최소 거리 노드를 이용하여 새로운 거리를 구함
반복
Ex. a에서 b로 바로 가면 7, a에서 c를 갔다가 b를 가면 3 -> a에서 b의 거리를 7에서 3으로 바꿈
배열을 사용하면 순차적으로 진행하기 때문에 시간복잡도는 N^2로 느리다.
힙(우선순위 큐)를 사용하면 최소 거리의 노드를 구하는 식이 LogN으로 단축된다.
즉 시간복잡도는 N*LogN으로 단축된다.
pair
서로 다른 두개의 자료형을 저장하는 자료구조-> 우선순위 큐에 pair 형식으로 데이터를 넣어줌
소스코드
https://github.com/kimdonwon/Algorithm/tree/master/Algorithm/src/Algorithm
