최단경로 구하는 알고리즘 : BFS , 다익스트라, 밸만포드 , SPFA, 플로이드와샬
< 분류 >
1) 음수 싸이클이 없는 경우 : BFS. 다익스트라
2) 음수 싸이클이 있는경우 : 밸만포드, SPFA(밸만포드 개선알고리즘)
3) 각 정점사이의 모든 최단경로 문제 : 플로이드와샬
SPFA( Shortest Path Faster Alogrithm)
: 음수사이클이 있거나 없거나 모두 사용할 수 있고, 밸만포드 시간복잡도가 O(|V||E|) 인데 반해 SPFA 는 시간복잡도가 O(|E|)임으로 훨씬 빠르게 구현할 수 있다. 뿐만 아니라 구현하는것도 어렵지 않다.
일반적으로 밸만포드와 같은 흐름의 알고리즘을 따르면서 , QUEUE를 우선순위 큐가 아닌 일반큐를 사용하고, 매번 dist 값은 업데이트하지만, queue에 이미 들어가있는 정점은 다시 큐에 넣지 않음으로써 구현할 수 있다.
int dis[1001]; bool inq[1001]; // 이미 큐에 들어있는 정점인지 확인하는 변수 queue<int> q; inq[a] = true; q.push(a); dis[a] = 0; while (!q.empty()) { int here = q.front(); q.pop(); inq[here] = false; int n = adj[here].size(); for (int i = 0; i < n; i++) { pdd there = adj[here][i]; if (dis[there.first] > dis[here] + there.second) { // 밸만포드 기본식 dis[there.first] = dis[here] + there.second; //update if (!inq[there.first]) { // 포함되지 않은 정점만 q에 넣는다. q.push(there.first); inq[there.first] = true; } } } } |
음수 사이클을 찾는 방법 :
음수싸이클이 있을때 경로 update가 무한대로 진행된다는 점을 이용한다. 정점의 갯수를 n이라할 때 해당정점의 dist[k] 가 n번이상 update 된다면 음수 사이클이 있다고 판별한다.
vistied[n] ={0, } 로 초기화
update 시 마다 visited[there.first] ++;
if( visitied[there.first] ==n) break; // 음수사이클