다익스트라 알고리즘은 다이나믹 프로그래밍을 이용한 대표적 최단 경로 탐색 알고리즘이다. ⇒ 최단거리는 여러개의 최단거리로 이루어짐. (특정 지점까지 거리 = A까지 가는 거리 + A에서 특정 지점까지 소요되는 거리)
따라서 특정 시작점에서 다른 모든 정점으로 가는 최단거리를 구할 수 있다.
단순하며 실행속도도 빠르다.
또한 다익스트라 알고리즘은 BFS를 이용하는 대표적인 알고리즘이다.
<aside> 💡 DFS는 한사람이 미로를 헤메는 과정이라면 BFS는 여러명이 각기 다른 갈림길로 흩어져 길을 찾는 법
</aside>
다익스트라는 여러명이 갈림길이 나올때마다 흩어져 찾다가 목적지에 가장 빨리 도착한 사람의 경로를 사용하는 것으로 볼 수 있다.
그래프를 인접 리스트의 형태로 구성하면 $O(|E|log(|V|))$의 시간복잡도로 구현할 수 있다.
❗주의 ❗ 음수 가중치가 있는 그래프 에서는 다익스트라가 올바르게 동작하지 않을 수 있습니다. 다익스트라에서는 dist중 가장 작은 값을 골랐을 때 그 값이 확실한 최단거리라는 보장이 되어야 하는데, 음수 가중치가 있으면 다시 골라졌던 정점에 도달하는 dist값이 더 작아질 수도 있기 때문에 최단거리임을 보장할 수 없게 됩니다.
K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. times배열안에 값들은 각각 출발지, 도착지, 소요시간 순으로 구성되며, 전체 노드의 개수는 N으로 입력받는다.
times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
2
이 문제는 고려해야할 사항이 두개 있다.
1번은 소요시간이 가장 큰 노드까지의 시간이라고 볼 수 있다. 소요시간이 가장 큰 노드까지의 최단시간을 구해야 한다.
2번은 모든 노드에서의 다익스트라 알고리즘 계산값 유무로 판별 가능한데, 노드가 8개인데 계산값이 7개뿐이라면 나머지 한 노드에는 도달할 수 없는 것이기에 -1을 리턴한다.