首页 > 代码库 > 最短路算法模板合集（Dijkstar，Dijkstar（优先队列优化）， 多源最短路Floyd）
最短路算法模板合集（Dijkstar，Dijkstar（优先队列优化）， 多源最短路Floyd）
再开始前我们先普及一下简单的图论知识
图的保存：
1.邻接矩阵。 G[maxn][maxn];
2.邻接表
邻接表我们有两种方式
（1）vector< Node > G[maxn];
这个是之前就定义了图的大小了，再下面使用的时候就不用对图的大小进行申请了， 但是因为是直接申请了大小
要对图进行初始化，因此可能在某些题目中这样使用的话会超时
（2）vector< vector<Node> > G;
这个是未定义大小，但是在使用之前要对其的大小内存进行申请。
G.resize(n+1);
Dijkstra‘s Algorithm
算法思想：
1.从源点出发源点所有能一步到达的点的距离更新，然后从除源点外的所有点之中找出距离源点最近的点。
2.然后更新我们之前所找到的最短路点所有连接的点，但是要求这个点未曾被当做最短点处理过
3.重复上述操作n次。
单源最短路 我们还可以对他进行优先队列优化下面是以HDU2544为模板的用Dijkstra‘s Algorithm
邻接矩阵版，不用优先队列优化
#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>using namespace std;#define INF 0xfffffff#define maxn 1002int G[maxn][maxn];//保存图int dist[maxn];//表示从起点到第i点的距离bool vis[maxn];//判断这个点是否被参观过int m, n;//边数 m 顶点数 nvoid Init(){ for(int i=0; i<=n; i++) { vis[i] = false; dist[i] = INF; for(int j=0; j<=i; j++) G[i][j] = G[j][i] = INF; }}int Dij(int Star,int End)//起点 --- 终点{ dist[Star] = 0; for(int i=1; i<=n; i++) { int index = 0, Min = INF; for(int j=1; j<=n; j++) { if( !vis[j] && Min > dist[j] )//找出没有被参观过，并且距离起点最近的点 Min = dist[j], index = j; } vis[index] = true; for(int j=1; j<=n; j++)//更新所有未曾到达的点距离，使之成为最近的点 { if( !vis[j] && dist[j] > dist[index] + G[index][j] ) dist[j] = dist[index] + G[index][j]; } } return dist[End];}int main(){ while(cin >> n >> m, m + n) { Init(); int a, b , c; for(int i=0; i<m; i++) { cin >> a >> b >> c; G[a][b] = min(G[a][b], c); G[b][a] = G[a][b]; } int ans = Dij(1,n); cout << ans << endl; } return 0;}接下来是邻接表版，用到了优先队列优化
1 #include <iostream> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 using namespace std;10 #define INF 0xfffffff11 #define maxn 100212 13 struct Node14 {15 int e;16 int w;17 friend bool operator < (Node A, Node B)18 {19 return A.w > B.w;20 }21 };22 23 bool vis[maxn];24 25 int m, n;26 vector< vector<Node> > G;27 28 int Dij(int Star,int End)29 {30 Node P, Pn;31 P.e = Star;32 P.w = 0;33 34 priority_queue<Node> Q;35 36 Q.push(P);37 38 while( !Q.empty() )39 {40 P = Q.top();41 Q.pop();42 43 if( vis[P.e] )44 continue;45 46 vis[P.e] = true;47 48 if( P.e == End )49 return P.w;50 51 int len = G[P.e].size();52 53 for(int i=0; i< len; i++)54 {55 Pn.e = G[P.e][i].e;56 Pn.w = G[P.e][i].w + P.w;57 58 if( !vis[Pn.e] )59 Q.push(Pn);60 }61 }62 return -1;63 }64 65 int main()66 {67 Node P;68 while(cin >> n >> m, m+n)69 {70 G.clear();71 G.resize(n+1);72 73 memset(vis,false,sizeof(vis));74 75 for(int i=0; i<m; i++)76 {77 int a, b, c;78 cin >> a >> b >> c;79 P.e = b;80 P.w = c;81 G[a].push_back(P);82 P.e = a;83 G[b].push_back(P);84 }85 86 int ans = Dij(1,n);87 88 cout << ans << endl;89 }90 return 0;91 }
下面是Floyd算法
Floyd是求多源最短路， 即可以求出所有点对之间的最短路
这个算法就只要注意两点就行了，初始化的时候 G[i][i] = 0, 其他的初始化为INF
#include <iostream>#include <cmath>#include <cstring>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>using namespace std;#define INF 0xfffffff#define maxn 1002int G[maxn][maxn];int dist[maxn][maxn];int m, n;void Floyd(){ for(int k=1; k<=n; k++) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { G[i][j] = min(G[i][j], G[i][k] + G[k][j]); } } }}void Init(){ for(int i=0; i<=n; i++) { G[i][i] = 0; for(int j=0; j<i; j++) G[i][j] = G[j][i] = INF; }}int main(){ while(cin >> n >> m, m+n) { Init(); for(int i=0; i<m; i++) { int a, b, c; cin >> a >> b >> c; G[a][b] = min(G[a][b],c); G[b][a] = G[a][b]; } Floyd(); cout << G[1][n] << endl; } return 0;}
最短路算法模板合集（Dijkstar，Dijkstar（优先队列优化）， 多源最短路Floyd）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。