• 참고 포스팅 링크

[알고리즘] 최단거리 알고리즘(Dijkstra,Floyd Warshall)

다익스트라 알고리즘

시작 노드에서 각각의 노드까지 도달하는 최단 경로를 구할 수 있는 알고리즘이다.

다익스트라 알고리즘은 DP와 그리디 알고리즘을 사용하여 문제를 해결한다.

• 아직 방문하지 않은 노드 중, 시작점으로 부터 가장 가까운 경로에 있는 노드를 먼저 방문한다. (그리디)
  • → 이 과정에서 해당 노드와 연결된 다른 노드들까지의 최단 경로를 계산한다.
  • → 해당 노드를 방문해서 도달하는 경우와, 해당 노드를 방문하지 않고 도달하는 경우를 비교하여 최단 경로를 갱신한다.
• 앞 과정을 반복한다.
  • → 앞 과정에서 갱신한 최단 경로를 토대로 다음 경로를 계산하면, 최단 경로를 구할 수 있다. (DP)

관련 문제 풀이

18352: 특정 거리의 도시 찾기

1446: 지름길

1753: 최단경로