By yusijia

Updated:

Contents
  1. 1. SPFA 邻接矩阵版
  2. 2. SPFA（链式前向星版）
  3. 3. 拓展：求DAG图上的单源最短路径

参考： 《图论及应用》 哈工大出版

SPFA 邻接矩阵版

  • SPFA可以适用于带负权的图，可以判负环(对于存在负环的图无法求单源最短路径)，有bfs和dfs两个版本，此模板是bfs的
  • SPFA可以用优先队列优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

//SPFA算法，是对bellman_ford算法的优化，采用队列，在队列中取点对其相邻的点进行松弛操作
//如果松弛成功且相邻的点不在队列中，就把相邻的点加入队列，被取的点出队，并把它的状态(是否在队列中)
//改为否，vis[i]=0,同一个节点可以多次进入队列进行松弛操作
//这样的题操作步骤：首先建立邻接矩阵，邻接矩阵初始化为inf,注意需要判断一下输入的边是否小于已有的边，取最小的那个，因为可能有重边,
//建立完邻接矩阵，写SPFA函数，dis[]数组初始化为inf,源点dis[start]=0

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
#define MAXN 110
#define INF 0x3f3f3f3f

int n, m;
int dis[MAXN];
int vis[MAXN];//某个节点是否已经在队列中
int mp[MAXN][MAXN];
int output[MAXN];

bool SPFA(int start)
{
    //第一步：建立队列，初始化vis,dis数组，并把源点加入队列中，修改其vis[]状态
    queue <int> q;
    memset(vis, 0, sizeof(vis));
    memset(dis, INF, sizeof(dis));
	memset(output, 0, sizeof(output));
    dis[start] = 0;
    q.push(start);
    vis[start] = 1;

//第二步：在队列中取点，把其vis状态设为0，对该点相邻的点（连接二者的边）进行松弛操作，修改相邻点的dis[]
//并判断相邻的点vis[]状态是否为0(不存在于队列中),如果是，将其加入到队列中

    while(!q.empty()){
        int from = q.front();
        q.pop();
        vis[from] = 0;//别忘了这一句
		output[from]++;
		if(output[from] > n) return false;
        for(int i = 1; i <= n; i++){
            if(dis[from] + mp[from][i] < dis[i]){
                dis[i] = dis[from] + mp[from][i];
                if(!vis[i]){//要写在松弛成功的里面
                    q.push(i);
                    vis[i]=1;
                }
            }
        }
    }
}

int main()
{
    while(cin >> n >> m && (n || m)){
        int from, to, w;
        memset(mp, INF, sizeof(mp));
        for(int i = 1; i <= m; i++){
            cin >> from >> to >> w;
            if(w < mp[from][to])
                mp[from][to] = mp[to][from] = w;
        }
        int start = 1;
        if(SPFA(start))
        	cout << dis[n] << endl;
    }

    return 0;
}

SPFA（链式前向星版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXnumNode = 110;
const int MAXnumEdge = 20000;

int numNode, numEdge;
int head[MAXnumNode];
int dis[MAXnumNode];
bool vis[MAXnumNode];
int output[MAXnumNode];

struct Edge{
	int to;
	int cost;
	int next;
}edge[MAXnumEdge];

void init()
{
	memset(vis, false, sizeof(vis));
	memset(dis, INF, sizeof(dis));
	memset(head, -1, sizeof(head));
	memset(output, 0, sizeof(output));
}

bool SPFA(int start)
{
	queue<int > que;
	que.push(start);
	vis[start] = true;
	dis[start] = 0;

	while(!que.empty()){
		int top = que.front();
		que.pop();
		vis[top] = false;
		output[top]++;//用来判断负环
		if(output[top] > numNode) return false;//某点弹出队列的次数超过n,则有负环
		for(int k = head[top]; ~k; k = edge[k].next){
			if(dis[edge[k].to] > dis[top] + edge[k].cost){
				dis[edge[k].to] = dis[top] + edge[k].cost;
				if(!vis[edge[k].to]){
					vis[edge[k].to] = true;
					que.push(edge[k].to);
				}
			}
		}
	}
	return true;
}

int main()
{
    //freopen("input.txt", "r", stdin);
	while(scanf("%d%d", &numNode, &numEdge) && (numEdge || numNode)){
		int from, to, cost;
		init();
		for(int i = 1; i <= numEdge * 2; i++){
			scanf("%d%d%d", &from, &to, &cost);
			edge[i].to = to;
			edge[i].cost = cost;
			edge[i].next = head[from];
			head[from] = i;

			i++;			//无向图,存边
			edge[i].to = from;
			edge[i].cost = cost;
			edge[i].next = head[to];
			head[to] = i;
		}
		int start = 1;
		if(SPFA(start))
			printf("%d\n", dis[numNode]);
	}
	return 0;
}

拓展：求DAG图上的单源最短路径

思路： 先找到入度为0的点为源点，如果有多个源点则选其中一个为源点，连条和其他源点的边权值为0，转化为一个源点，再用拓扑排序求出拓扑序列，然后结合SPFA求出源点到其他点的最短路径

1
2
3
4
5
6
7
8
9
10

int dis[MAXN];
memset(dis, INF, sizeof(dis));
dis[1] = 0;
for(int i = 0; i < queSize; i++){
    for(int k = head[que[i]]; ~k; k = edge[k].next){
        if(dis[edge[k].to] > dis[que[i]] + edge[k].cost)
            dis[edge[k].to] = dis[que[i]] + edge[k].cost
    }
}
Contents
  1. 1. SPFA 邻接矩阵版
  2. 2. SPFA（链式前向星版）
  3. 3. 拓展：求DAG图上的单源最短路径