这可能是个愚蠢的问题，但为什么复杂度不取决于图中存在的边的权重？
最佳答案
有许多不同的图形算法，在某些情况下，复杂性确实取决于边权重。例如，Ford-Fulkerson max-flow algorithm具有运行时间 O(mF)，其中 F 是最大可能流，它取决于边的最大容量。其他算法(如 Dijkstra 算法)的运行时间与边长无关，因为在计算模型中假设对这些权重的操作始终需要时间 O(1)。
一般而言，具有依赖于图中边的权重/容量/长度的运行时的算法通过基于这些边的容量/权重/长度迭代多次来获得它们的依赖性。如果算法仅对权重等进行数值计算，则通常不存在依赖关系，因为算术运算通常只被认为需要时间 O(1)，除非有理由相信不是这样。
希望这对您有所帮助!
关于algorithm - 图算法的复杂性对边权重的依赖性？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19871917/