Dijkstra 알고리즘

 

❒ Description

---

743. Network Delay Time 문제를 풀면서 Dijkstra 알고리즘을 복습했다. 

이 알고리즘은 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. 

 

풀이방법은 총 3가지 였다.

1. 배열 내에서 선형탐색 + 배열 내에 중복 정점 허용하지 않음
2. 우선순위큐 내에서 최솟값 탐색 + 우선순위큐 내에 중복 정점 허용하지 않음
3. 우선순위큐 내에서 최솟값 탐색 + 우선순위큐 내에 중복 정점 허용

 

 

※ 참고
나무위키(다익스트라 알고리즘)을 보면 잘 정리되어 있어서 별도로 정리하지 않음.
소스 코드 : 링크

 

 

관련 문제
743. Network Delay Time
787. Cheapest Flights Within K Stops
778. Swim in Rising Water
815. Bus Routes
1091. Shortest Path in Binary Matrix
1631. Path With Minimum Effort
2812. Find the Safest Path in a Grid
2642. Design Graph With Shortest Path Calculator

 

 

 

 

 

 

---