数据结构 — 图 之 MPT(最短路径 — dijkstra算法 )
发布日期:2021-06-30 19:49:33
浏览次数:2
分类:技术文章
本文共 531 字,大约阅读时间需要 1 分钟。
【描述】: 无向图的最短路径 — Dijkstra(适用于非负权值边)
【输入】:
【输出】:
顶点 距离(与源点)
0 0
1 3
2 5
3 4
4 4
/* Dijkstra(不适用于负权值的边)*/#includeusing namespace std;/* 宏定义 */#define INFINITY 65535#define MAX_NUM 100#define EleType int/* 定义一些需要的变量 */bool visit[MAX_NUM]; //顶点i 是否已经走过了int dist[MAX_NUM]; //源点到 顶点i 的距离const int vertices = 5; //顶点数/* 定义图 */int graph[vertices][vertices] = { { 0,3,6,5,0 }, { 3,0,0,1,1 }, { 6,0,0,1,1 }, { 5,1,1,0,1 }, { 0,1,1,1,0 }};/* 通过dist数组得出得出当下到源点的最小顶点 */int getMin() { int min = INFINITY; int minIndex; for(int i = 0; i
转载地址:https://lipenglin.blog.csdn.net/article/details/50016513 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月06日 13时17分11秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
ACM-ICPC 2018 焦作赛区网络预赛 I. Save the Room
2019-04-30
CodeForces - 987C Three displays (暴力/dp)
2019-04-30
计蒜客 NAIPC 2016 F. Mountain Scenes(dp)
2019-04-30
牛客国庆集训派对Day4——I 连通块计数(思维)
2019-04-30
牛客国庆集训派对Day4——G 区间权值(找规律,双重前缀和)
2019-04-30
牛客国庆集训派对Day5——L 数论之神(找规律/数论)
2019-04-30
CodeForces - 629B Far Relative’s Problem(模拟)
2019-04-30
CodeForces - 1059B Forgery (思维)
2019-04-30
CodeForces - 456C Boredom (dp)
2019-04-30
CodeForces - 960B Minimize the error (思维,贪心)
2019-04-30
CodeForces - 97B Superset (思维/分治/构造)
2019-04-30
CodeForces - 675A Infinite Sequence(简单数论 细节)
2019-04-30
CodeForces - 1042B Vitamins (思维)
2019-04-30
ACM 2013 长沙区域赛 Alice's Print Service (二分 思维)
2019-04-30
ACM 2013 长沙区域赛 Collision (几何)
2019-04-30