hellogaon

벨만 포드(Bellman Ford)는 간선에 비용이 있는 그래프에서시작점부터 다른 정점까지의 최단거리를 구할 수 있는 단일 시작점 최단거리 알고리즘입니다.이는 다익스트라 알고리즘과 동일하지만 간선의 비용이 음수일 때도 사용할 수 있습니다.벨만 포드 알고리즘은 다익스트라와 동일하게 dist배열을 사용하며 dist[i]는 시작점에서 i번 정점까지의 최단거리를 뜻합니다.시작점의 dist값은 0, 나머지 모든 정점은 무한대로 초기화 한 뒤 dist배열을 갱신하는 작업을 진행하는데최단 거리는 정점 개수가 V일 때 최대 V-1개의 간선을 거쳐야 한다는 원리를 이용하여V-1번의 루프를 돌며 k번째 루프에서는 시작점으로부터 k개의 간선을 거쳐 도달할 수 있는 최단 경로를 dist에 저장합니다.이 때 최단 거리가 V개 ..