迪杰斯特拉 (Dijkstra)算法求最短路径问题

目录 算法介绍 应用实例 算法步骤 代码实现 算法介绍 迪杰斯特拉( Dijkstra )算法是典型最短路径算…

目录

算法介绍

应用实例

算法步骤

代码实现


算法介绍

迪杰斯特拉( Dijkstra )算法是典型最短路径算法,用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。

应用实例

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rGC5LiN6ISx5Y-R,size_20,color_FFFFFF,t_70,g_se,x_16

算法步骤

1)设置出发顶点为 v ,顶点集合 VfvI ,v2, vi .), v 到 V 各顶点的距离构成距离集合 Dis , Dis ( dI ,d2, di .), Dis 集合记录着 v 到图中各顶点的距离(到自身可以看作0, v 到 vi 距离对应为 di )
2)从 Dis 中选择值最小的 di 并移出 Dis 集合,同时移出 V 集合中对应的项点 vi ,此时的 v 到 vi 即为最短路径
3)更新 Dis 集合,更新规则为:比较 v 到 V 集合中顶点的距离值,与 v 通过 vi 到 V 集合中顶点的距离值,保留
值较小的一个(同时也应该更新顶点的前驱节点为 vi ,表明是通过 vi 到达的)
4)重复执行两步骤,直到最短路径顶点为目标顶点即可结束。

代码实现

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/8267.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部