最短路径

比眉伴天荒 2022-08-01 13:59 268阅读 0赞

最短路径的迪杰斯特拉算法跟最小生成树的普利姆算法很像！

但是这里的像只是代码相似，实质是不一样的！

普利姆算法是从任意点开始，找到跟他最近的点记录距离，然后

从这一点出发一次找最短的距离，直到循环结束！所以用于在n

个点找出n-1条路径将它们连接起来！

而迪杰斯特拉算法从任一点开始找到未访问的点到这个点的距

离，然后记录最小的！（说到这你感觉这不是一样的吗？）然

后，依次更新其他点到这一点的最小距离，（因为有的点与他不

挨边，但是通过这一点也许就挨边了！）更新之后再次比较未访

问的点到这一点的距离！（他所求的是所有的点到这一点的最小

距离）所以可以求图中任意一点到这一点的最小距离，最小生成

树就做不到！这里你明白了吗？

至于迪杰斯特拉算法怎么实现的，我们来看一下！

Dijkstra最短路径算法

Dijkstra最短路径算法

跟这个意思差不多！

发表评论

表情：
评论列表 （有 0 条评论，268人围观）

还没有评论，来说两句吧...

相关阅读

    相关 最短路径

    最短路径 最短路径是指俩顶点之间经过的边上的权值之和和最少的路径。 Dijkstra算法 按路径长度递增的次序产生最短路径的算法。 比如有下面这样一个图，要求v

    缺乏、安全感缺乏、安全感/ 0 赞/ 63 阅读

    相关 最短路径

    最短路径的迪杰斯特拉算法跟最小生成树的普利姆算法很像！   但是这里的像只是代码相似，实质是不一样的！   普利姆算法是从任意点开始，找到跟他最近的点记录距离，然后

    比眉伴天荒比眉伴天荒/ 0 赞/ 269 阅读

    相关 最短路径

    floyd算法 最简单的最短路径算法，可以计算图中任意两点间的最短路径  folyd算法的时间复杂度是O(N3),如果是一个没有边权的图，把相连的两点  间的距离设为dis

    系统管理员系统管理员/ 0 赞/ 319 阅读