알고리즘

음수 사이클이 없는 그래프에서 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘이다.다익스트라 알고리즘과 다르게 음수 사이클만 존재하지 않으면 음의 가중치를 가질 수 있다.음수 사이클 : 사이클의 모든 경로의 합이 음수가 되는 사이클1 → 2 → 1 사이클\-

다익스트라 알고리즘은 최단 경로(Shortest Path) 탐색 알고리즘이다.입력 그래프는 양수의 가중치 그래프이다.BFS 알고리즘은 가중치가 1인 그래프에만 적용되지만 다익스트라는 1보다 커도 된다.프림(Prim)의 MST 알고리즘과 흡사한 과정으로 진행된다.차이점P