SPFA.cpp

#include <cstdio>		// printf
#include <cstdlib>		// NULL
#include <algorithm>		// fill
#include <vector>
#include <queue>

using namespace std;

//use constant instead of macro
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

class LIB_SPFA{
public:

	LIB_SPFA(unsigned int v=MAXV, unsigned int e=MAXV*(MAXV-1)) 
		: neg_cycle(false), checked_start(INVALID), Vnum(v), Enum(e<v*(v-1)?e:v*(v-1)), edge(Vnum+1), prev(Vnum+1), dis(Vnum+1)
	{}

	void add_edge(int src, int dst, int weight)
	{
		edge[src].push_back(EDGE(dst,weight));

		checked_start = INVALID;
	}

	bool contains_neg_cycle(int src=1)
	{
		if(checked_start == INVALID)
			SPFA(src);
		return neg_cycle;
	}

	int get_dis(int src, int dst)
	{
		if(contains_neg_cycle(src))
			return INVALID;
		if(checked_start != src)
			SPFA(src);
		return dis[dst];
	}

	const vector<int>& getPrev() const {return prev;}

private:

	struct EDGE{
		EDGE(int n, int w):next(n),w(w){}
		int next, w;
	};

	bool neg_cycle;
	int checked_start;

	int Vnum, Enum;
	vector< vector<EDGE> > edge;
	vector<int> prev;
	vector<int> dis;

	void SPFA(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
	LIB_SPFA 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 = %d\n", src, dst, graph.get_dis(src,dst));
	else
		printf("The graph contains negetive cycles.\n");

	return 0;
}