'벨만포드' 태그의 글 목록

최단경로 알고리즘에는 다익스트라, 벨만포드, 플로이드 워셜 ... 이 가장 대표적인 알고리즘이다. 이번 포스팅은 벨만포드에 대해 알아보도록 하겠다. 이미 다익스트라 알고리즘을 알고있는 상태에서 왜 벨만포드 알고리즘이 따로 존재하고, 사용되는 것일까? 다익스트라 알고리즘와 벨만포드 알고리즘은 둘다 최단거리를 구할 수 있는 알고리즘임에 분명하다. 하지만 두 알고리즘에는 차이점이 존재한다. 다익스트라 알고리즘의 단점을 생각해보면 알 수 있다. 다익스트라 알고리즘은, 모든 간선의 길이가 양수(+)일때 최단거리를 보장한다. 혹여나 음수(-)의 간선이 존재한다면.. 최단거리를 구할 수 있지 못할 수도 있다. 벨만포드는 이러한 다익스트라의 단점을 해결할 수 있는 최단거리 알고리즘이다. 즉, 간선이 어떤 형태 ( 양수..

알고리즘 2023. 4. 10. 11:41

이전 1 다음