【floyd算法求两个顶点的最短路径时,pathk-1一定是pathk的子集。】这句话对不对?

k-1和k均为下标。没财富值了,见谅。。
2025-03-21 10:02:07
推荐回答(3个)
回答1:

不对,Floyd是从一个顶点开始比较,k是在k-1的基础上加入了一个新顶点比较,新加入的顶点有可能改变了最短路径,记录了路径的path也随之改变

回答2:

是错的,可能k-1时经过点A,但是k时有一条不需要通过点A的路径,这时候path更新为path_k,点A不在path_k上,所以不是子集。

回答3:

因为实现佛罗里达算法需要3个for循环,所以时间复杂度为O(n*n*n).至于具体算法过程及实现方法,那就看你是不是学过图论了。