Bellman-Ford 썸네일형 리스트형 9. 최단 경로 탐색: 벨만-포드 알고리즘(Bellman-Ford Algorithm) 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 최단 경로 탐색 알고리즘입니다. 노드와 가중치가 포함된 간선 정보를 이용하여 시작점과 도착점 사이의 최단 거리를 찾는 것이 이 알고리즘의 목적입니다. 설명만 들어서는 다익스트라 알고리즘과 일치합니다. 하지만 기본적인 최단 경로 탐색 알고리즘의 조건과 목적에 더하여 벨만-포드 알고리즘은 특정한 조건을 포함하고 있을 때 사용됩니다. 가중치에 음수가 포함된 경우입니다. 다익스트라 알고리즘은 기본적으로 가중치가 양수와 0으로 이루어져 있다는 것을 가정하고 있습니다. 그렇기 때문에 음수 가중치가 포함되어있다고 해도 알고리즘 자체에서 음수 가중치 부분을 처리할 수 없습니다. 벨만-포드 알고리즘의 원리는 다음과 같습니다. 우리가 특정 노드에서 다른 어떤 노드로 이.. 이전 1 다음