archives

https://www.acmicpc.net/problem/11657 이 카테고리의 바로 앞 다익스트라 알고리즘은 기본적으로 간선에 음수가 없다는 가정의 알고리즘이다. 하지만 이 문제의 벨만 포드 알고리즘은 간선에 음수가 있을수도 있다고 생각한다. 벨만 포드 알고리즘 : http://qkqhxla1.tistory.com/668 #include #include #include using namespace std; const long long INF = 999999999; int n,m,u,v,w; vector adj[801]; vector bellmanford(int src) { vector dist(501,INF); dist[src] = 0; int updated; for(int k=0;kn>>m; for..

잘 설명된 블로그 : http://kks227.blog.me/220796029558 (알고리즘 설명이 진짜 잘 되있네요) 앞의 다익스트라 알고리즘은 a에서 b로 갈때 가중치가 음수가 아니라고 가정한 상태에서 코딩을 한다. 하지만 이 벨만 포드 알고리즘으로 가중치가 음수일 경우까지 판별이 가능하다. 음수 검사까지 하므로 시간복잡도는 늘어나서 O(VE)이다. 사진은 역시 저 블로그에서 가져왔다. 0에서 2까지 가는 최소거리를 찾을때 다익스트라 알고리즘은 음수가 아니라고 가정한 상태이므로 8로 최소값을 잡는다. 그런데 진짜 최소거리는 1을 거쳐서 가는 5다. 이러한 음수판별까지하는게 벨만 포드 알고리즘이다. 그런데 음의 가중치가 있는 그래프를 판별시 항상 무한대 사이클을 염두해 두어야 한다.이 무한대 사이클을..