기본 개념
다익스트라, 벨만-포드 알고리즘은 모두 최단 경로(Shortest Path)를 찾는 알고리즘이다.
전에 봤던 MST를 찾는 프림, 크루스칼 알고리즘과 비슷한 구조를 가진것처럼 보이지만 서로 수행하는 목적이 다르다. 알아보기 앞서, 최소 신장 트리(Minimum Spanning Tree, MST)와 최단 경로(Shortest Path)의 특징들을 비교해보니 해당 알고리즘들에 대한 이해에 도움이 되었다.
동작원리
다익스트라 알고리즘 (dijkstra)
다익스트라 알고리즘은 그리디 알고리즘을 기반으로 한 알고리즘이다.
그리디 알고리즘 : 현재의 상황에서 가장 최적의 선택을 함으로써 전체 문제의 최적해를 찾는 알고리즘
다익스트라 알고리즘은 시작 정점에서 출발하여 방문하지 않은 정점 중에서 최단 거리가 가장 짧은 정점을 선택하여 탐색을 진행한다. 이 과정을 반복하여 모든 정점에 대한 최단 거리를 찾는다.
벨만-포드 알고리즘 (bellman-ford)
벨만포드 알고리즘은 동적 계획법을 기반으로 한 알고리즘이다.
동적 계획법(Dynamic Programming) : 큰 문제를 작은 문제들로 나누어 해결하는 알고리즘
모든 간선을 순서대로 확인하며 모든 정점 간의 최단 거리를 갱신한다. 이 과정을 반복하여 모든 정점에 대한 최단 거리를 찾는다.
다익스트라 (dijkstra) vs 벨만-포드 (bellman-ford)
참고 : https://www.baeldung.com/cs/dijkstra-vs-bellman-ford\
https://www.researchgate.net/figure/Comparative-analysis-of-the-Dijkstra-and-Bellman-Ford-algorithms_tbl1_367472939
