图上最短路(Dijkstra, spfa)

单源最短路径

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

输入样例

输出样例

单源最短路（Single-Source Shortest Paths, SSSP）

先上Dijkstra算法

Dikstra 算法适用于边权为正的情况。主要想法是：将一个点走一步能到达的所有结点都放进队列里，并从队列里选择源点到该点路径最短的结点出队。这样就保证出队的结点一定是源点到该点的最短路。那么就能确定放进队列的每一个结点不仅要有该结点的编号，也要有源点到该结点的距离，所以可以用结构体来实现。队列中出队的必须是最小的，那么就可以用优先队列实现。所以开一个结构体优先队列。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<vector>
 8 using namespace std;
 9 const int maxn = 1e4 + 5;
10 const int INF = 2147483647;
11 struct Grap
12 {
13     int num, cost;    //num点编号，cost到该点距离 
14     bool operator < (const Grap& other)const    
15     /*优先队列出队的原本是最大的，而我们期望的是最小的,所
16     以重载小于号，不仅要兼容结构体，还要使逻辑相反 */ 
17     {
18         return cost > other.cost;
19     }
20 }; 
21 vector<int>v[maxn];
22 vector<int>c[maxn];
23 int n, m, k, vis[maxn], dis[maxn];
24 void dijkstra(int k)
25 {
26     for(int i = 0; i < maxn; ++i)    
27         dis[i] = INF;
28     /*初始化设为无穷，同时也代表了源点无法到达的点
29     的最短路径长度就是无穷*/
30     memset(vis, 0, sizeof(vis));
31     priority_queue<Grap>q;
32     q.push((Grap){k, 0});
33     dis[k] = 0;
34     while(!q.empty())
35     {
36         Grap now = q.top(); q.pop();
37         int node = now.num;
38         if(vis[node]) continue;
39         /*如果该点已经出队，那到这个点的路径长度一定是最短路。为了防止
40         结点的重复扩展，如果发现新取出来的结点曾经被取出来过，应该直接
41         把它扔掉，所以开一个数组记录。 */
42         vis[node] = 1;
43         for(int i = 0; i < v[node].size(); ++i)
44         {
45             if(dis[v[node][i]] > dis[node] + c[node][i])
46             {
47                 dis[v[node][i]] = dis[node] + c[node][i];
48                 
49                 q.push((Grap){v[node][i], dis[v[node][i]]});
50             }
51         }
52     }
53 }
54 int main()
55 {
56     scanf("%d%d%d", &n, &m, &k);
57     for(int i = 0; i < m; ++i)
58     {
59         int a, b, cost; scanf("%d%d%d", &a, &b, &cost);
60         v[a].push_back(b); c[a].push_back(cost);    //用vector建图 
61     }
62     dijkstra(k);
63     for(int i = 1; i <= n; ++i) printf("%d%s",dis[i], i == n ? "\n" : " ");
64     return 0;
65 }

再上一个spfa算法

spfa算法不仅可以求最短路，也可以判断一个图中存不存在负圈。在这个算法中，一个结点可能多次入队（出队），最多入队 n 次（结点个数次），而当超过 n 次时，就证明一定存在负圈。

 1 #include <cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<queue>
 5 #include<vector>
 6 #include<cstring>
 7 #include<algorithm>
 8 using namespace std;
 9 vector<int>v[10005], c[10005];
10 const int INF = 2147483647;
11 int dis[10005];
12 bool vis[10005];
13 void spfa(int a)    
14 {
15     for(int i = 0; i < 10005; ++i) dis[i] = INF;
16     dis[a] = 0;
17     memset(vis, 0, sizeof(vis));
18     queue<int>q;q.push(a);
19     while(!q.empty())
20     {
21         int now = q.front();q.pop();
22         vis[now] = 0;    //出队后去除标记 
23         for(int i = 0; i < (int)v[now].size(); ++i)
24         {
25             if(dis[now] + c[now][i] < dis[v[now][i]])
26             {
27                 dis[v[now][i]] = dis[now] + c[now][i];
28                 if(!vis[v[now][i]])
29                     {q.push(v[now][i]); vis[v[now][i]] = 1;}
30             }
31         }
32     }
33 }
34 int main()
35 {
36     int n, m, s;
37     scanf("%d%d%d", &n, &m, &s);
38     for(int i = 0; i < m; ++i)
39     {
40         int f, g, w;
41         scanf("%d%d%d", &f, &g, &w);
42         v[f].push_back(g);c[f].push_back(w);    
43     }
44     spfa(s);
45     for (int i = 1; i <= n; i++) printf("%d%c", dis[i], i == n ? '\n' : ' ');
46 }