Bellman-Ford Algorithm (1) 썸네일형 리스트형 [Algorithm] Bellman-Ford Algorithm (벨만 포드 알고리즘) 1. Bellman-Ford Algorithm 벨만 포드 알고리즘은 다익스트라 알고리즘과 같이 한 정점으로부터 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과의 차이점은 음수 가중치를 가진 간선이 그래프에 존재해도 적용이 가능하다는 점이다. 그러나 음수 간선이 사이클을 이루는 경우에는 최단 거리를 찾을 수 없기 때문에 동작하지 않는다. 벨만 포드 알고리즘은 두 경로 사이의 최단 경로를 구할 때 모든 간선을 대상으로 edge relaxation을 수행한다. edge relaxation은 두 경로 사이에 더 가까운 경로가 있다면 해당 경로의 거리로 간선을 경감하는 작업이다. 그래프에서 s, u 두 정점 사이의 최단 거리 경로는 s -> u로의 바로 연결되는 간선을 통한 경로일 수도.. 이전 1 다음