[알고리즘/C++] 최단 경로 찾기 - 벨만-포드 알고리즘(Bellman-Ford)

그래프에서 최단 경로를 찾는 방법은 대표적인 알고리즘 문제 중의 하나이다. 그 중 하나가 벨만-포드(Bellman-Ford) 알고리즘이다. 위와 같은 형태의 그래프가 있다고 했을 때, 노드 1에서 노드 4까지 가는 최단 경로는 노드 3을 거치면 4가 된다. 벨만 포드 알고리즘을 노드 갯수-1 크기 만큼의 라운드를 순회하여 특정 노드에서 나머지 노드들까지의 최단 경로를 찾는 알고리즘이다. typedef vector vecTup; void bellmanFord(vecTup grap, vi& distance, int start){ for (int i = 0; i < distance.size(); i++) { distance[i] = 100; } distance[start] = 0; for (int i = 0;..

2023.08.03