首页 / 算法 / Dijkstra算法模板

Dijkstra算法模板

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Dijkstra算法模板，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2842字，纯文字阅读大概需要5分钟。

内容图文

自己对Dijstra算法的理解是：

  1. 首先输入保存点，边的权值（注意无向图和有向图在保存时的区别）。
  2. 将表示从起点st到顶点 i 的距离的d[ i ]数组的每一个值初始化为INF，令d[st] = 0。
  3.  遍历d[ ]数组的下标 i （即顶点 i）这个操作是通过优先队列来实现的，然后遍历以顶点 i 为起点的边，更新d[ i ]的最小值。
  4. 最后直接访问d[en]，即可得到最短距离。

通过模板题来熟悉一下这个算法吧，最短路之HDU2544

技术分享图片 技术分享图片 
                 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <vector>
 6 #include <queue>
 7 #include <algorithm>
 8#define INF 0x3f3f3f3f
 9#define FRE() freopen("in.txt","r",stdin)
1011usingnamespace std;
12 typedef longlong ll;
13 typedef pair<int,int> P;//first是距离，second是点的编号14constint maxn = 150;
15int d[maxn];//数组d[i]表示从起点s到顶点 i 的最短距离16int n,m;
17struct edge
18{
19     edge(int t,int c):to(t),cost(c){}
20int to;//表示这条边的终点21int cost;//该边的权重22};
23 vector<edge> G[maxn];//储存以下标i为起点的边24 priority_queue<P,vector<P>,greater<P> > que;//遍历d[]数组的下标，更新最小值2526void init()
27{
28for(int i = 0; i < maxn; i++)
29        G[i].clear();
30for(int i = 0; i < m; i++)
31    {
32int st,en,c;
33         scanf("%d%d%d",&st,&en,&c);
34         G[st].push_back(edge(en,c));//这是个无向图注意储存的方式35        G[en].push_back(edge(st,c));
36    }
37}
3839int main()
40{
41//FRE();42while(scanf("%d%d",&n,&m) && n+m)
43    {
44        init();
45for(int i = 0; i < maxn; i++)
46             d[i]= INF;
47         d[1] = 0;//起点到起点本身的距离为048         que.push(P(0, 1));
49while(!que.empty())
50        {
51             P p = que.top();
52            que.pop();
53int v = p.second;
54if(d[v] < p.first) continue;
55for(int i = 0; i < G[v].size(); i++)
56            {
57                 edge e = G[v][i];
58if(d[e.to] > d[v] + e.cost)
59                {
60                     d[e.to] = d[v] + e.cost;
61                    que.push(P(d[e.to],e.to));
62                }
63            }
64        }
65         printf("%d\n",d[n]);
66    }
67return0;
68 }
View Code

另外还有一个用二维数组的写法：

技术分享图片 技术分享图片 
                 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4#define INF 0x3f3f3f3f
 5 6usingnamespace std;
 7constint maxn = 100;
 8 9int e[maxn][maxn];
10int dis[maxn],vis[maxn];
11int n,m;
1213void init()
14{
15for(int i = 1; i <= n; i++)
16    {
17for(int j = 1; j <= n; j++)
18        {
19             e[i][j] = INF;
20        }
21    }
22int a,b,c;
23for(int i = 0; i < m; i++)
24    {
25         scanf("%d%d%d",&a,&b,&c);
26         e[a][b] = c;
27         e[b][a] = c;
28    }
29for(int i = 1; i <= n; i++)//算出1到各个点的距离30    {
31         dis[i] = e[1][i];
32         vis[i] = 0;
33    }
34     vis[1] = 1;
35}
3637void Dij()
38{
39for(int i = 1; i <= n; i++)
40    {
41int mmin = INF;
42int u;
43for(int j = 1; j <= n; j++)
44        {
45if(!vis[j] && dis[j] < mmin)
46            {
47                 mmin = dis[j];
48                 u = j;
49            }
50        }
51         vis[u] = 1;
52for(int j = 1; j <= n; j++)
53        {
54if(!vis[j] && dis[j] > e[u][j] + dis[u])
55            {
56                 dis[j] = e[u][j] + dis[u];
57            }
58        }
59    }
60}
6162int main()
63{
64while(scanf("%d%d",&n,&m) && (m + n))
65    {
66        init();
67        Dij();
68         printf("%d\n",dis[n]);
69    }
70return0;
71 }
View Code

 

原文：https://www.cnblogs.com/sykline/p/9737817.html

内容总结

以上是互联网集市为您收集整理的Dijkstra算法模板全部内容，希望文章能够帮你解决Dijkstra算法模板所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1150942.html

来源：【匿名】