最短路径dijkstra算法

 我来答
insistDO2027
2023-06-08 · TA获得超过493个赞
知道大有可为答主
回答量:6208
采纳率:99%
帮助的人:90.7万
展开全部

最短路径dijkstra算法如下:

Dijkstra迪杰斯特拉是一种处理单源点的最短路径算法,就是说求从某一个节点到其他所有节点的最短路径就是Dijkstra。

资料拓展:

迪杰斯特拉算法(Dijkstra)是由荷兰数腔计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其薯纳衫余各顶点的最短路径算法,解决的是有权图中最短路径问题。

迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。

Dijkstra算法一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN,CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

将T中顶点按递增的次序加入到S中,保证:从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度。每个顶点对应一个距离值。

S中顶点:从V0到此顶点的长度。T中顶点:从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度。依据:可以证明V0到T中顶点Vk的,或是从V0到Vk的直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和。

初始时令S={V0},T=V-S={其余顶点},T中顶点对应的距离值。若茄搭存在,d(V0,Vi)为弧上的权值。若不存在,d(V0,Vi)为∞。

从T中选取一个与S中顶点有关联边且权值最小的顶点W,加入到S中。对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值。重复上述步骤2、3,直到S中包含所有顶点,即W=Vi为止。

推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式