11657

[c++] 백준 11657 풀이 ( 타임머신, 최단경로, 벨만-포드, 음수 가중치 )

우선 이 문제를 풀기위해서는 벨만-포드 알고리즘을 이해해야한다. 벨만-포드 단일시작점 알고리즘 (출발 노드가 고정) 최단 경로 알고리즘 음수 간선 가능 음수 사이클 확인 가능 쓱 보면 다익스트라와 비슷해보인다.(https://guccin.tistory.com/112?category=977502) 그러나 다익스트라와 달리 벨만-포드 알고리즘은 음수 간선에 대해서 최단거리를 알아낼수 있다. 또한 다익스트라는 우선순위 큐를 활용하여 최단 경로를 구하는데에 반해 벨만-포드는 매번 모든 간선을 전부 확인하며 최단거리를 알아내기 때문에 다익스트라보다 시간복잡도가 크다. 다익스트라 O(|E||log|V|), 벨만-포드 O(|E||V|) [c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 ) ..