图论 - 单源最短路 - Djikstra算法实现练习(最短路)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了图论 - 单源最短路 - Djikstra算法实现练习(最短路),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2663字,纯文字阅读大概需要4分钟。
内容图文
![图论 - 单源最短路 - Djikstra算法实现练习(最短路)](/upload/InfoBanner/zyjiaocheng/836/d182f582a79f483697f7c13a40e9d6da.jpg)
最短路
时间限制:4 sec
空间限制:256 MB
问题描述
给定一张 n 个点的无向带权图,节点的编号从 1 至 n,求从 S 到 T 的最短路径长度。
输入格式
第一行 4 个数 n,m,S, T,分别表示点数、边数、起点、终点。
接下来 m 行,每行 3 个正整数 u,v,w,描述一条 u 到 v 的双向边,边权为 w。
保证 1<=u,v<=n。
输出格式
输出一行一个整数,表示 S 到 T 的最短路。
样例输入
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
样例输出
7
数据范围
本题共设置 12 个测试点。
对于前 10 个测试点,保证 n<=2500,m<=6200,对于每条边有 w<=1000。这部分数据有梯度。
对于所有的 12 个测试点,保证 n<=100,000,m<=250,000。
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路
这是典型的单源最短路问题,可以使用Dijkstra算法。Dijkstra算法原理见该文。
C++代码
#include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <utility> #include <vector> using namespace std; const int MAXNV = 100005; // 最大顶点数 const int MAXNE = 250005; // 最大边数 bool visited[MAXNV]; // visited[i]记录了从源点到顶点i的最短路是否已经求得了。 long long dist[MAXNV]; // dist[i]记录了从源点到顶点i的最短距离,初始值为一较大值。 vector<vector<pair<int, int> > > edge; // edge[i]:记录顶点i的所有邻接边,pair的第一个元素为终点,第二个元素为权重 struct myComp { bool operator()(const pair<int, long long> & p1, const pair<int, long long> & p2) const { return p1.second > p2.second; } }; /* Dijkstra算法求src到dst的最短路径长度 */ long long shortestDist(int src, int dst) { memset(visited, 0, sizeof(bool)*MAXNV); // 初始化各顶点均为尚未求得最短距离 memset(dist, 127, sizeof(long long)*MAXNV); // 初始化从src到各点的最短距离为很大的值 priority_queue<pair<int, long long>, vector<pair<int, long long> >, myComp > q; dist[src] = 0; q.push(make_pair(src, 0)); while ( !q.empty() ) { pair<int, long long> p = q.top(); q.pop(); int v = p.first; long long w = p.second; if ( visited[v] ) // 若已经求得到v的最短距离 continue; visited[v] = true; dist[v] = w; for ( auto it = edge[v].begin(); it != edge[v].end(); ++it ) if ( !visited[it->first] ) { dist[it->first] = min(dist[it->first], w + it->second); q.push(make_pair(it->first, dist[it->first])); } } return dist[dst]; } int main() { int nv = 0, ne = 0; // 顶点数,边数 int src = 0, dst = 0; // 源点,终点 scanf("%d %d %d %d", &nv, &ne, &src, &dst); edge.resize(nv+1); for ( int i = 0; i < ne; ++i ) { int u, v, w; scanf("%d %d %d", &u, &v, &w); edge[u].push_back(make_pair(v, w)); edge[v].push_back(make_pair(u, w)); } long long ans = shortestDist(src, dst); printf("%lld\n", ans); return 0; }
内容总结
以上是互联网集市为您收集整理的图论 - 单源最短路 - Djikstra算法实现练习(最短路)全部内容,希望文章能够帮你解决图论 - 单源最短路 - Djikstra算法实现练习(最短路)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。