1. 다익스트라 vs 벨만-포드 vs 플로이드-워셜

[[dijkstra]]{다익스트라} [[bellman-ford]]{벨만-포드} [[floyd-warshall]]{플로이드-워셜}
  • 한 정점에서 나머지 정점들의 최단 거리
  • 음수 가중치 불가능 (무한 루프)
  • Min-Heap 방식(priorty queue로 구현)
  • 가장 짧은 거리의 정점부터 연산
  • 시간 복잡도 : O((V+E)logV)
     
     
     
  • 한 정점에서 나머지 정점들의 최단 거리
  • 음수 가중치 가능
  • 음수 사이클 발견 가능
  • 기본 아이디어는 다익스트라와 비슷
    • 모든 정점의 최단 거리를 구할 때까지 모든 간선들을
      여러 번 확인하여 최단 거리를 구한다.
    • 다익스트라보다 느림
  • 시간 복잡도 : O(V*E)
  • 모든 정점 사이의 최단 거리
  • 다익스트라 V번 수행하는 것보다 빠름
  • 시간 복잡도 : O(V^3) (단, V는 장점의 개수)
  • 정점쌍 (i, j)에 대해 정점 k 경유지를 거쳤을 때 더 빠른 경우 갱신
  • dp[i][j]는 정점 i에서 정점 j 까지의 최단 거리