Java教程

最短路

本文主要是介绍最短路，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

带有负环的图是没有最短路径的

SPFA：权值可以为负数，但是时间复杂度过高 O(VE) ，
可以判断是否有负环，如果某个点进入队列的次数超过N次则存在负环（N为图的顶点数）
Dijkstra：广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，采用贪心的策略
Kruskal: 基于并查集的贪心算法,以边为对象，不断地加入新的不构成回路的最短边来构成最小生成树。
Prim: 从任意一个顶点开始，每次选择一个与当前顶点集最近的一个顶点，并将两顶点之间的边加入到树中，在找当前最近顶点时使用到了贪心算法。

这篇关于最短路的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航