求A到B之间的最短路径,怎么获取

发布网友发布时间：2022-05-01 23:02

共1个回答

热心网友时间：2022-04-26 19:51

问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径。解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法，另外还有著名的启发式搜索算法A*，不过A*准备单独出一篇，其中Floyd算法可以求解任意两点间的最短路径的长度。任意一个最短路算法都是基于这样一个事实：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点到B。
(1) 迪杰斯特拉(Dijkstra)算法按路径长度(看下面表格的最后一行，就是next点)递增次序产生最短路径。先把V分成两组：
S：已求出最短路径的顶点的集合
V-S=T：尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到S中，依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值或是从V0经S中顶点到Vk的路径权值之和（反证法可证，说实话，真不明白哦）。
(2) 求最短路径步骤
初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值，若存在<V0,Vi>，为<V0,Vi>弧上的权值（和SPFA初始化方式不同），若不存在<V0,Vi>，为Inf。
从T中选取一个其距离值为最小的顶点W(贪心体现在此处)，加入S(注意不是直接从S集合中选取，理解这个对于理解vis数组的作用至关重要)，对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值（上面两个并列for循环，使用最小点更新）。
重复上述步骤，直到S中包含所有顶点，即S=V为止（说明最外层是除起点外的遍历）。