迪杰斯特拉算法

答案:1 悬赏:20 手机版

解决时间 2021-03-28 12:43

提问者网友：杀生予夺
2021-03-28 07:45

迪杰斯特拉算法

最佳答案

五星知识达人网友：西岸风
2021-03-28 09:12

按路径长度递增次序产生最短路径算法：
把V分成两组：（1）S：已求出最短路径的顶点的集合
（2）V-S=T：尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到S中，
保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度
（2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）求最短路径步骤 … 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值 ƒ 若存在，为弧上的权值 ƒ 若不存在，为∝ … 从T中选取一个其距离值为最小的顶点W，加入S … 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值 … 重复上述步骤，直到S中包含所有顶点，即S=V为止

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！