-
-
Save pcyu16/403029 to your computer and use it in GitHub Desktop.
SPFA
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * SPFA - Shortest Path Faster Algorithm | |
| */ | |
| #include <cstdio> // printf | |
| #include <cstdlib> // NULL | |
| #include <algorithm> // fill | |
| #include <vector> | |
| #include <queue> | |
| using namespace std; | |
| const int MAXV = 1000; // maximum value of vertex | |
| const int INF = 1000000000; // infinity value used instead of INT_MAX for relax may overflow | |
| const int INVALID = 0xDEADF00D; // special value to record negetive cycle condiction | |
| template<class weight_t> | |
| class SPFA{ | |
| public: | |
| SPFA(int v=MAXV, int e=MAXV*(MAXV-1)) | |
| : neg_cycle(false), checked_start(INVALID), Vnum(v), Enum(e), edge(Vnum+1), prev(Vnum+1), dis(Vnum+1) | |
| {} | |
| void add_edge(int src, int dst, weight_t weight) | |
| { | |
| edge[src].push_back(EDGE(dst,weight)); | |
| checked_start = INVALID; | |
| } | |
| bool contains_neg_cycle(int src=1) | |
| { | |
| if(checked_start == INVALID) | |
| SPFA_run(src); | |
| return neg_cycle; | |
| } | |
| weight_t get_dis(int src, int dst) | |
| { | |
| if(contains_neg_cycle(src)) | |
| return INVALID; | |
| if(checked_start != (int)src) | |
| SPFA_run(src); | |
| return dis[dst]; | |
| } | |
| const vector<int>& getPrev() const {return prev;} | |
| private: | |
| struct EDGE{ | |
| EDGE(int n, weight_t w):next(n),w(w){} | |
| int next; | |
| weight_t w; | |
| }; | |
| bool neg_cycle; | |
| int checked_start; | |
| int Vnum, Enum; | |
| vector< vector<EDGE> > edge; | |
| vector<int> prev; | |
| vector<weight_t> dis; | |
| void SPFA_run(int start) | |
| { | |
| int i; | |
| int nowv, nextv, siz; | |
| queue<int> check; | |
| vector<int> count(Vnum+1); | |
| vector<bool> inqueue(Vnum+1); | |
| checked_start = start; | |
| fill(prev.begin(), prev.begin()+Vnum+1, -1); | |
| fill(dis.begin(), dis.begin()+Vnum+1, INF); | |
| fill(inqueue.begin(), inqueue.begin()+Vnum+1, false); | |
| fill(count.begin(), count.begin()+Vnum+1, 0); | |
| dis[start] = 0; | |
| check.push(start); | |
| inqueue[start] = true; | |
| count[start]++; | |
| while(!check.empty()){ | |
| nowv = check.front(); | |
| check.pop(); | |
| inqueue[nowv] = false; | |
| siz = edge[nowv].size(); | |
| for(i=0;i<siz;i++){ | |
| nextv = edge[nowv][i].next; | |
| if(dis[nextv] > dis[nowv] + edge[nowv][i].w){ | |
| dis[nextv] = dis[nowv] + edge[nowv][i].w; | |
| prev[nextv] = nowv; | |
| if(!inqueue[nextv]){ | |
| check.push(nextv); | |
| inqueue[nextv] = true; | |
| count[nextv]++; | |
| if(count[nextv] >= Vnum ){ | |
| neg_cycle = true; | |
| return ; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| neg_cycle = false; | |
| } | |
| }; | |
| int main() | |
| { | |
| int v=5, e=7; | |
| // e can be ignored | |
| // if v is ignored, default value MAXV is used | |
| SPFA<double> graph(v,e); | |
| graph.add_edge(1,2,2); | |
| graph.add_edge(2,1,2); | |
| graph.add_edge(1,3,4); | |
| graph.add_edge(3,1,4); | |
| graph.add_edge(2,3,1); | |
| graph.add_edge(3,2,1); | |
| graph.add_edge(3,1,-3); | |
| int src=1, dst=2; | |
| // contain_neg_cycle will check paths from vertex 1 | |
| if(graph.contains_neg_cycle()) | |
| printf("The graph contains negetive cycles.\n"); | |
| else | |
| printf("The graph doesn't contain negetive cycles.\n"); | |
| if(graph.get_dis(src,dst) != INVALID ) | |
| printf("The shortest path length from %d to %d = %lf\n", src, dst, graph.get_dis(src,dst)); | |
| else | |
| printf("The graph contains negetive cycles.\n"); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment