목록벨만포드 (1)

algoqna

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

- 한 노드에서 다른 노드까지의 최단 경로를 구할 때 사용하는 알고리즘 - 다익스트라의 경우 양수일 때만 작동 가능하다는 점, 벨만 포드는 음수의 가중치가 있을 때 사용하는 것으로 알고 있으면 된다. - 필요한 것은 dist배열 (어떤 지점까지의 최단경로를 저장할 배열) 1) 모든 정점의 개수 -1(V-1)만큼 반복하여 2) 각 정점과 연결되있는 간선들을 파악한다 - 현재 내가 있는 곳이 INF값이 아니고 내가 있는 지점을 거쳐서 다음 지점을 가는 비용이 다음 지점의 비용보다 낮다면 갱신 3) 위의 과정을 딱 1번 더 수행하고, dist의 배열이 변경된다면 음수 사이클이 존재한다는 의미임. - 만약 음수사이클이 존재한다면 기존에 갱신되있는 dist배열이 변경되기 때문. - 정점의 개수 (V번) 반복에 대..
프로그래밍/알고리즘 개념 2023. 4. 14. 20:22
이전 Prev 1 Next 다음