[leetcode] 743. Network Delay Time
🏃 다익스트라 최단 경로 알고리즘
특정 노드에서 출발해서 다른 모든 노드로 가는 최단 경로를 계산한다.
- 가중치가 있는 그래프에서 가장 짧은 경로를 찾을 때 사용하는 알고리즘
- 다익스트라 알고리즘의 가중치는 양수여야 한다.
- 다익스트라 알고리즘은 매 상황에서 비용이 가장 적은 노드를 선택하는 과정이 반복되므로 그리디 알고리즘으로 분류된다.
- 거리를 기록하는 테이블에 거리값을 매 번 최소값으로 업데이트하므로 DP로도 분류된다.
🌟 다익스트라 알고리즘 동작 과정
- 준비하기
- 거리 기록 테이블을 INF로 초기화한다.
- 노드를 방문했는지 판단하는 visited 리스트를 모두 False로 초기화한다.
(노드를 방문했다 = 해당 노드의 최단 경로를 발견했다 = 리스트 값을 True로 바꿔준다 = 땅땅땅! 출발 노드로부터 지금 노드까지의 최단거리이다 = 더이상 탐색하지 않는다)
- 출발 노드를 설정한다. 출발 노드를 선택했다면 거리 기록 테이블에서 출발 노드는 0으로 바꿔준다. (출발노드에서 출발노드까지 거리는 0이므로)
땅땅땅! 이 노드는 더 이상 최단경로를 볼 필요가 없으니 visited 리스트에서 True로 바꿔준다 - 출발 노드와 연결된 노드들의 거리값을 갱신해준다.
- 갱신된 노드들 중에서 거리가 가장 작은 노드를 선택한다.
-> 땅땅땅! (visited = True로 바꿔주고) 방금 선택한 노드는 출발 노드에서 시작하여 가장 짧게 이동할 수 있는 노드이다. - 3에서 선택한 노드와 연결된 노드들의 거리값을 갱신해준다.
어떻게 갱신해주냐.
- (1)이전에 기록되어있던 값과 (2)출발지~3에서 선택한 노드 ~ 연결노드 두 가지 선택지 중에서 뭐가 더 거리가 작은지 비교하고, 작은 값으로 업데이트 해주면 된다.
- 업데이트된 노드들 중에서 가장 작은 노드를 선택한다.
-> 땅땅땅! (visited = True로 바꿔주고) 출발지로부터 6번에서 선택한 노드까지 가장 짧게 걸리는 최단 거리를 발견했다! - 4번~5번 과정을 계속 반복해주면 된다. 언제까지? 더 이상 탐색할 노드가 없으 때까지!
