floyd算法适合所有的带权有向图?这句话是错的 为什么

floyd算法适合所有的带权有向图?这句话是错的 为什么
这句话是错的 为什么
愚知 1年前 已收到1个回答 举报
赞

发条收音机 幼苗

共回答了16个问题采纳率：87.5% 举报

　Floyd算法适用于APSP(All Pairs Shortest Paths),是一种动态规划算法,稠密图效果最佳,边权可正可负.此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra算法时间复杂度 比较高,不适合计算大量数据

1年前 追问

8

愚知 举报

边权为负 意义何在

举报 发条收音机

每次都找一个距源点最近的点（dmin），然后将该距离定为这个点到源点的最短路径（d[i]<--dmin）；但如果存在负权边，那就有可能先通过并不是距源点最近的一个次优点（dmin'），再通过这个负权边L(L<0)，使得路径之和更小（dmin'+L
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.012 s. - webmaster@yulucn.com