三种最短路并邻接表的模板

邻接表

struct node {
	int value, ed;//value:值 ed:对应的点 
	node *next;//下一个 
}sa[MAXN + 5];

void push (int x, int y, int z) {//插入边 
	node *p = new node;
	
	p->next = sa[x].next;
	p->ed = y;
	p->value = z;
	sa[x].next = p;
	
	return;
}

Floyd

void Floyd (int n) {
	for (int k = 1; k <= n; k ++) {//枚举k， 表示经过小于等于k的点的最短路 
		for (int i = 1; i <= n; i ++) {//枚举两个端点 
			if (s[i][k] >= INF) {//如果有不连通的两个点就直接跳过 
				continue;
			}
			for (int j = 1; j <= n; j ++) {
				if (s[k][j] >= INF) {
					continue;
				}
				if (s[i][k] + s[k][j] < s[i][j]) {//如果经过k点要近一些， 就经过k点 
					s[i][j] = s[i][k] + s[k][j];
				}
			}
		}
	}
} 
void Floyd_empty (int n) {//在输入之前将所有点赋初值 
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			if (i != j) {//自己到自己的距离为0， 其他的暂时赋极大值表不连通 
				s[i][j] = INF;
			}
			else {
				s[i][j] = 0;
			}
		}
	}
}

dijkstra

void dijkstra (int h, int n) {//h:起始节点 n:节点个数 
	priority_queue , vector  >, greater  > > Q;//小根堆维护最小值 
	
	for (int i = 1; i <= n; i ++) {//先赋初值为极大值， 表示与起点无连接 
		s[i] = INF;
	}
	s[h] = 0;//自己与自己距离为0 
	Q.push (make_pair (0, h));//加入优先队列 
	while (!Q.empty ()) {
		pair  a = Q.top ();//拿出堆顶 
		
		Q.pop ();
		if (vis[a.second]) {//如果这个节点已被拿出过就不再用此节点更新其他节点 
			continue;
		}
		else {
			vis[a.second] = 1;//否则用此节点进行更新， 并标记已被拿出过 
		}
		for (node *i = sa[a.second].next; i != 0; i = i->next) {//遍历此节点的相邻节点 
			if (i->value + a.first < s[i->ed]) {//如果松弛成功 
				s[i->ed] = i->value + a.first;
				Q.push (make_pair (i->value + a.first, i->ed));//加入堆 
			}
		}
	}
	
	return ;
}

SPFA

优先队列优化

bool SPFA_check (int h, int n) {//判负环 
	priority_queue , vector  >, greater  > > q;//优先队列优化 
	
	for (int i = 1; i <= n; i ++) {//把所有的点压进堆， 求出图中是否存在负环 
		q.push (make_pair (0, i));
		vis[i] = 0;
		s[i] = 0;//因为求的是负环， 所以直接设为0， 减少时间复杂度 
	}
	vis[h] = 1;
	while (!q.empty ()) {
		pair  a = q.top ();
		
		q.pop ();
		vis[a.second] = 0;
		for (node *i = sa[a.second].next; i != 0; i = i->next) {
			if (i->value + s[a.second] < s[i->ed]) {//判断是否能松弛 
				s[i->ed] = i->value + s[a.second];
				num[i->ed] ++;
				if (num [i->ed] >= n) {//比较更新次数， 判断是否存在负环 
					return 0;
				}
				if (!vis[i->ed]) {
					q.push (make_pair (s[i->ed], i->ed));
				}
			}
		}
	}
	
	return 1;
}
bool SPFA (int h, int n) {
	priority_queue , vector  >, greater  > > q;
	
	for (int i = 1; i <= n; i ++) {
		vis[i] = 0;
		s[i] = INF;
		num[i] = 0;
	}
	q.push (make_pair (0, h));
	vis[h] = 1;
	s[h] = 0;
	while (!q.empty ()) {
		pair  a = q.top ();
		
		q.pop ();
		vis[a.second] = 0;
		for (node *i = sa[a.second].next; i != 0; i = i->next) {
			if (i->value + s[a.second] < s[i->ed]) {
				s[i->ed] = i->value + s[a.second];
				f[i->ed] = a.second;//保存路径（同样适用于其他单源最短路算法）
				num[i->ed] ++;
				if (num [i->ed] >= n) {//直接调用此函数， 可以求出起始点可以到达的负环 
					return 0;
				}
				if (!vis[i->ed]) {
					q.push (make_pair (s[i->ed], i->ed));
				}
			}
		}
	}
	
	return 1;
}

无优先队列优化

bool SPFA_check (int h, int n) {
	queue  q;
	
	for (int i = 1; i <= n; i ++) {
		q.push (i);
		vis[i] = 0;
		s[i] = 0;
	}
	vis[h] = 1;
	while (!q.empty ()) {
		int a = q.front ();
		
		q.pop ();
		vis[a] = 0;
		for (node *i = sa[a].next; i != 0; i = i->next) {
			if (i->value + s[a] < s[i->ed]) {
				s[i->ed] = i->value + s[a];
				num[i->ed] ++;
				if (num [i->ed] >= n) {
					return 0;
				}
				if (!vis[i->ed]) {
					q.push (i->ed);
				}
			}
		}
	}
	
	return 1;
}
bool SPFA (int h, int n) {
	priority_queue , greater  > q;//若无输出字典序最小的要求， 可换成queue
	
	for (int i = 1; i <= n; i ++) {
		vis[i] = 0;
		s[i] = INF;
		num[i] = 0;
	}
	q.push (h);
	vis[h] = 1;
	s[h] = 0;
	while (!q.empty ()) {
		int a = q.top ();
		
		q.pop ();
		vis[a] = 0;
		for (node *i = sa[a].next; i != 0; i = i->next) {
			if (i->value + s[a] < s[i->ed]) {
				s[i->ed] = i->value + s[a];
				f[i->ed] = a;
				num[i->ed] ++;
				if (num [i->ed] >= n) {
					return 0;
				}
				if (!vis[i->ed]) {
					q.push (i->ed);
				}
			}
		}
	}
	
	return 1;
}

dfs版(由于此方法不适用查最短路， 只适用于判负环， 所以只给出判负环代码)

bool SPFA_dfs (int h) {
	vis[h] = 1;
	bool bl = 1;
	for (node *i = sa[h].next; i != 0; i = i->next) {
		if (i->value + s[h] < s[i->ed]) {
			s[i->ed] = i->value + s[h];
			if (vis[i->ed]) {//若可以再次更新一个已经更新过的值， 那么就有负环（因为初值都是0）
				return 0;
			}
			bl &= SPFA_dfs (i->ed);
			if (!bl) {
				return 0;
			}
		}
	}
	return 1;
}
bool SPFA_check (int h, int n) {
	
	for (int i = 1; i <= n; i ++) {
		s[i] = 0;
		vis[i] = 0;
	}
	
	for (int i = 1; i <= n; i ++) {
		if (!vis[i]) {
			if (!SPFA_dfs (i)) {
				return 0;
			}
		}
	}
	return 1;
}

单源最短路路径输出（保存路径见SPFA中f数组）

void print (int h, int t) {
	if (h == t) {
		printf ("%d ", t);
		return ;
	}
	else {
		print (h, f[t]);
		printf ("%d ", t);
	}
}