Sims의 문제해결 저장소

다익스트라, 벨만포드, 플로이드 워셜 ... 다 최단거리를 구하는 대표적인 알고리즘이다. 하지만 '최단거리'를 구한다는 공통적인 목표가 있지만, 각자 서로 다른 특징이 있기에 여러 알고리즘이 나눈다. 1. 다익스트라 장점 : 양의 간선이 존재할때 빠르게 최단거리를 구할 수 있다. 단점 : 음의 간선이 존재할때는 최단거리를 보장할 수 없다. 2. 벨만포드 장점 : 음의 간선이 존재할때 최단거리를 구할 수 있다. 단점 : 음의폐로가 존재할 수 있다. / 시간이 오래걸린다. 3. 플로이드 워셜 장점 : 하나의 정점에서 시작하여 다른 정점의 최단거리를 구하는 것이 아닌, 모든 정점을 기준으로 각 정점에 최단거리를 구한다. 단점 : 시간이 오래 걸린다. 위처럼 장/단점이 존재하기에 여러 최단거리 알고리즘이 있는데..

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