210709 벨만-포드(Bellman-Ford), 다익스트라(Dijkstra)

최단 경로(Shortest Path)를 찾는 대표적인 알고리즘들 중 일부

벨만-포드(Bellman-Ford)

벨만포드는 가중치가 음수일 경우에도 사용가능 ( 다익스트라와의 차이점 )

 

1.  초기화 : 간선 검사 순서 임의로 정하는 등등
2.  앞서 정한 순서대로 모든 간선 확인하며 Relax ( 정점에 기존 보다 더 낮은 가중치로 도달할 수 있으면 값 갱신 == 최단거리 값 갱신) 해줌
3.  정점의 개수 - 1 번 만큼 반복

 

 

시간복잡도 :  ( 간선의 개수 ) * ( 정점의 개수 -1 ) => O ( 간선의 개수 * 정점의 개수 )

 

다익스트라(Dijkstra)

 

Greedy 알고리즘이라고 할 수 있음

그래프 내의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단경로를 구하는 알고리즘

효율적, 실생활에서 많이 사용됨 ex) gps, 길찾기 서비스 등

But 간선의 가중치가 음수인 것이 있다면 사용불가

 

1. 집합 S 를 정의하여 공집합으로 초기화한다. S는 값이 확정된 정점의 집합을 의미 또한 최단 경로를 표시하는 배열 초기화 (초기에는 최단 경로를 구하지 않은 상태이기에 무한대로 표시, 실제로는 아주 큰 값으로 사용)
2.  시작 정점에서부터 인접한 정점으로 가는 가중치와 배열이 저장하고 있는 값과 비교 후 더 작은 값으로 갱신, 정점 S로 빼며 값을 확정시킨다.
3.  이전 정점에서부터 거리가 가장 짧은 정점을 잡고 2번의 과정을 반복
4.  2,3 번 과정을 모든 정점 확정시킬 때까지 반복한다.

 

시간복잡도 : 우선 순위 큐를 활용하여 거리가 가장 짧은 노드를 고르는 과정 O(log (간선의 개수)) 

을 정점의 개수 만큼 반복하기에 O(정점의 개수 * log (간선의 개수))