최단 경로 알고리즘 정리

최단 경로 알고리즘에는 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드 와샬 알고리즘이 있다.

 

다익스트라 알고리즘(Dijkstra's algorithm)

그래프의 어떤 정점 하나를 시작점으로 선택 -> 나머지 정점들로의 최단경로를 모두 구한다.

정점 개수 V, 간선 개수 E일 때 시간 복잡도: O(ElogV)

weight(cost)의 값은 항상 0 이상이어야 한다. 만약 0 미만인 경우 벨만-포드 알고리즘을 사용하면 된다.

참고: https://m.blog.naver.com/kks227/220796029558

 

벨만-포드 알고리즘(Bellman-Ford Algorithm)

그래프의 어떤 정점 하나를 시작점으로 선택 -> 나머지 정점들로의 최단경로를 모두 구한다.

정점 개수 V, 간선 개수 E일 때 시간 복잡도: O(VE)

weight(cost)의 값이 음수일 때도 사용할 수 있다. 또한, 음수 간선의 순환을 감지할 수 있다.

알고리즘 진행 순서

1. 출발 노드 설정 2. INF로 최단 거리 테이블 초기화(시작점은 0으로 초기화) 3. 다음의 과정을 N-1번 반복     3-1. 전체 간선 E개를 하나씩 확인     3-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 4. 만약 음수 간선 순환 발생 여부를 확인하고 싶다면, 3번 과정을 1번 더 수행하여 최단 거리 테이블 갱신 여부를 확인

 

 

참고: https://m.blog.naver.com/kks227/220796963742

 

플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)

정점 V개가 있고 거리가 다 주어져 있을 때 단 한 번의 시행으로 모든 정점 쌍 사이의 거리를 다 구해낸다. 3중 for문으로 구현된다. weight(cost)의 값이 음수일 때도 사용할 수 있다.

정점 개수 V일 때 시간 복잡도: O(V^3)

참고: https://m.blog.naver.com/kks227/220797649276