【hdu 2544最短路】【Dijkstra算法模板题】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【hdu 2544最短路】【Dijkstra算法模板题】,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2137字,纯文字阅读大概需要4分钟。
内容图文
![【hdu 2544最短路】【Dijkstra算法模板题】](/upload/InfoBanner/zyjiaocheng/737/71e15cb0765b4bdb8ba5f1f17d183deb.jpg)
Dijkstra算法
分析
Dijkstra算法适用于边权为正的情况。它可用于计算正权图上的单源最短路( Single-Source Shortest Paths, SSSP) , 即从单个源点出发, 到所有结点的最短路(这样最后返回你想要的那个节点对应的距离即可)。 该算法同时适用于有向图和无向图。
其伪代码如下:
清除所有点的标号
设d[0]=0, 其他d[i]=INF //INF被定义为一个很大的数字
循环n次 {
在所有未标号结点中, 选出d值最小的结点x
给结点x标记
对于从x出发的所有边(x,y), 更新d[y] = min{d[y], d[x]+w(x,y)} //w(x,y)是指边xy对应的权值
}
模板
可以根据上面的伪代码帮助理解
int Dijk()
{
memset(vis, 0, sizeof(vis));
memset(d, 0, sizeof(d));
for(int i = 1; i <= N; i++)
d[i] = ((i == 1) ? 0 : INF); //注意这里INF一定要设置的很大 //这里的条件设置根据题意自行判断
for(int i = 1; i <= N; i++)
{
int x, minn = INF;
for(int j = 1; j <= N; j++)
{
if(!vis[j] && d[j] < minn) //在所有未标号结点中, 选出d值最小的结点x
{
minn = d[j];
x = j;
}
}
vis[x] = 1; //标记它
for(int y = 1; y <= N; y++)
d[y] = min(d[y], d[x] + route[x][y]);
}
return d[...]; //根据题意要求进行返回相应的值
}
以上内容参考自刘汝佳的《算法竞赛入门经典》
题目链接
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100 + 10;
const int INF = 0x3f3f3f3f;
int N, M;
int a, b, c;
int route[maxn][maxn], d[maxn];
int vis[maxn];
int Dijk()
{
memset(vis, 0, sizeof(vis));
memset(d, 0, sizeof(d));
for(int i = 1; i <= N; i++)
d[i] = ((i == 1) ? 0 : INF); //这里的条件设置根据题意自行判断
for(int i = 1; i <= N; i++)
{
int x, minn = INF;
for(int j = 1; j <= N; j++)
{
if(!vis[j] && d[j] < minn) //在所有未标号结点中, 选出d值最小的结点x
{
minn = d[j];
x = j;
}
}
vis[x] = 1; //标记它
for(int y = 1; y <= N; y++)
d[y] = min(d[y], d[x] + route[x][y]);
}
return d[N];
}
void init()
{
for(int i = 1; i <= N; i++)
{
for(int j = i + 1; j <= N; j++)
route[i][j] = route[j][i] = INF;
}
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
while(cin >> N >> M && N && M)
{
init();
for(int i = 0; i < M; i++)
{
cin >> a >> b >> c;
route[a][b] = route[b][a] = c;
}
int minn = Dijk();
cout << minn << endl;
}
}
内容总结
以上是互联网集市为您收集整理的【hdu 2544最短路】【Dijkstra算法模板题】全部内容,希望文章能够帮你解决【hdu 2544最短路】【Dijkstra算法模板题】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。