最短路 淡淡的烟草味﹌ 2022-03-18 12:35 274阅读 0赞 最短路 典型用途:交通网络的问题——从甲地到乙地之间是否有公路连通?在有多条通路的情况下,哪一条路最短? 交通网络用有向网来表示:顶点——表示城市,弧——表示两个城市有路连通,弧上的权值——表示两城市之间的距离、交通费或途中所花费的时间等。 如何能够使一个城市到另一个城市的运输时间最短或运费最省?这就是一个求两座城市间的最短路径问题。 问题抽象:在有向网中A点(源点)到达B点(终点)的多条路径中,寻找一条各边权值之和最小的路径,即最短路径。最短路径与最小生成树不同,路径上不一定包含n个顶点,也不一定包含n - 1条边。 常见最短路径问题:单源点最短路径、所有顶点间的最短路径 (1)如何求得单源点最短路径? 穷举法:将源点到终点的所有路径都列出来,然后在其中选最短的一条。但是,当路径特别多时,特别麻烦;没有规律可循。 迪杰斯特拉(Dijkstra)算法:按路径长度递增次序产生各顶点的最短路径。 路径长度最短的最短路径的特点: 在此路径上,必定只含一条弧 <v\_0, v\_1>,且其权值最小。由此,只要在所有从源点出发的弧中查找权值最小者。 下一条路径长度次短的最短路径的特点: ①、直接从源点到v\_2<v\_0, v\_2>(只含一条弧); ②、从源点经过顶点v\_1,再到达v\_2<v\_0, v\_1>,<v\_1, v\_2>(由两条弧组成) 再下一条路径长度次短的最短路径的特点: 有以下四种情况: ①、直接从源点到v\_3<v\_0, v\_3>(由一条弧组成); ②、从源点经过顶点v\_1,再到达v\_3<v\_0, v\_1>,<v\_1, v\_3>(由两条弧组成); ③、从源点经过顶点v\_2,再到达v\_3<v\_0, v\_2>,<v\_2, v\_3>(由两条弧组成); ④、从源点经过顶点v\_1 ,v\_2,再到达v\_3<v\_0, v\_1>,<v\_1, v\_2>,<v\_2, v\_3>(由三条弧组成); 其余最短路径的特点: ①、直接从源点到v\_i<v\_0, v\_i>(只含一条弧); ②、从源点经过已求得的最短路径上的顶点,再到达v\_i(含有多条弧)。 Dijkstra算法步骤: 初始时令S=\{v\_0\}, T=\{其余顶点\}。T中顶点对应的距离值用辅助数组D存放。 D\[i\]初值:若<v\_0, v\_i>存在,则为其权值;否则为∞。 从T中选取一个其距离值最小的顶点v\_j,加入S。对T中顶点的距离值进行修改:若加进v\_j作中间顶点,从v\_0到v\_i的距离值比不加 vj 的路径要短,则修改此距离值。 重复上述步骤,直到 S = V 为止。 算法实现: void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D) { // 用Dijkstra算法求有向网 G 的 v0 顶点到其余顶点v的最短路径P[v]及带权长度D[v]。 // 若P[v][w]为TRUE,则 w 是从 v0 到 v 当前求得最短路径上的顶点。 P是存放最短路径的矩阵,经过顶点变成TRUE // final[v]为TRUE当且仅当 v∈S,即已经求得从v0到v的最短路径。 int v,w,i,j,min; Status final[MAX_VERTEX_NUM]; for(v = 0 ;v < G.vexnum ;++v) { final[v] = FALSE; D[v] = G.arcs[v0][v].adj; //将顶点数组中下标对应是 v0 和 v的距离给了D[v] for(w = 0;w < G.vexnum; ++w) P[v][w] = FALSE; //设空路径 if(D[v] < INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; } } D[v0]=0; final[v0]= TRUE; /* 初始化,v0顶点属于S集 */ for(i = 1;i < G.vexnum; ++i) /* 其余G.vexnum-1个顶点 */ { /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */ min = INFINITY; /* 当前所知离v0顶点的最近距离 */ for(w = 0;w < G.vexnum; ++w) if(!final[w]) /* w顶点在V-S中 */ if(D[w] < min) { v = w; min = D[w]; } /* w顶点离v0顶点更近 */ final[v] = TRUE; /* 离v0顶点最近的v加入S集 */ for(w = 0;w < G.vexnum; ++w) /* 更新当前最短路径及距离 */ { if(!final[w] && min < INFINITY && G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w])) { /* 修改D[w]和P[w],w∈V-S */ D[w] = min + G.arcs[v][w].adj; for(j = 0;j < G.vexnum;++j) P[w][j] = P[v][j]; P[w][w] = TRUE; } } } }
相关 最短路 <table> <tbody> <tr> <td> <h2>最短路</h2> <strong>Time Limit: 5000/1000 MS (Java/O 向右看齐/ 2024年02月18日 22:54/ 0 赞/ 61 阅读
相关 最短路 \[hdu 1599\] ([http://acm.hdu.edu.cn/showproblem.php?pid=1599][http_acm.hdu.edu.cn_showp 红太狼/ 2022年08月04日 08:28/ 0 赞/ 179 阅读
相关 C--最短路 Problem Description 给出一个带权无向图,包含n个点,m条边。求出s,e的最短路。保证最短路存在。 Input 多组输入。 对于每组数据。 以你之姓@/ 2022年07月12日 08:26/ 0 赞/ 138 阅读
相关 最短路 队列+松弛操作 读取队头顶点u,并将队头顶点u出队(记得消除标记);将与点u相连的所有点v进行松弛操作,如果能更新估计值(即令d\[v\]变小),那么就更新,另外,如果 忘是亡心i/ 2022年06月11日 04:06/ 0 赞/ 224 阅读
相关 最短路 一下模板均已通过HDUOJ 2544 程序设计竞赛队空间和时间复杂度要求都很高,所以朴素的Dijkstra[算法][Link 1]无论时间还是空间,效率都很低。 所以,一般 淡淡的烟草味﹌/ 2022年06月09日 04:28/ 0 赞/ 258 阅读
相关 最短路径(Dijkstra)-HDU 2544-最短路 最短路径(Dijkstra)-HDU 2544-最短路 -------------------- 题目链接: [最短路][Link 1] 亦凉/ 2022年05月14日 03:38/ 0 赞/ 232 阅读
相关 最短路 最短路 典型用途:交通网络的问题——从甲地到乙地之间是否有公路连通?在有多条通路的情况下,哪一条路最短? 交通网络用有向网来表示:顶点——表示城市,弧——表示两个城 淡淡的烟草味﹌/ 2022年03月18日 12:35/ 0 赞/ 275 阅读
相关 最短路 Floyed [http://codevs.cn/problem/1077/][http_codevs.cn_problem_1077] include<cstdi ﹏ヽ暗。殇╰゛Y/ 2021年11月18日 00:30/ 0 赞/ 309 阅读
相关 最短路 复习下图论算法 1. 邻接表的Dijkstra ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] / 冷不防/ 2021年11月02日 14:24/ 0 赞/ 466 阅读
相关 HDU 2544 最短路 最短路 时间限制:5000/1000 MS(Java / Others)内存限制:32768/32768 K(Java /其他) 提交总数:106773接受提交内容: 桃扇骨/ 2021年10月18日 08:20/ 0 赞/ 344 阅读
还没有评论,来说两句吧...