2022-08-01 TIL

 

 

☝ 다익스트라 최단 경로 알고리즘

• 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 다른 노드로 가는 최단 경로를 구하는 알고리즘
• '음의 간선'이 없을 때 정상적으로 동작
• 음의 간선은 0보다 작은 값을 가지는 간선을 의미
• 그리디 알고리즘으로 분류됨
• 다익스트라 최단 경로 알고리즘 원리
  1. 출발 노드 설정
  2. 최단 거리 테이블을 초기화
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
  4. 해당 노드를 거쳐 다른 노드로 가능 비용을 계산해 최단 거리 테이블을 갱신
  5. 3-4번 과정을 반복
• 간단한 다익스트라 알고리즘의 시간 복잡도 👉 O(V²) (V는 노드의 개수)
• 개선된 다익스트라 알고리즘의 시간 복잡도 👉 O(ElogV) (V는 노드의 개수, E는 간선의 개수)
• 개선된 다익스트라 알고리즘은 힙 자료구조를 사용

 

 

☝ 플로이드 워셜 알고리즘

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘
• 플로이드 워셜 알고리즘의 시간 복잡도 👉 O(N³)
• 플로이드 워셜 알고리즘은 다이나믹 프로그래밍
• 문제의 범위가 한정적인 경우(대략 500개 이하) 플로이드 워셜 알고리즘을 사용하고,
  이상인 경우 다익스트라 알고리즘을 사용한다.