Question

几个关于数据结构中图的问题！

1.用prim算法求最小生成树时，边上的权怎么不能为负呢？不是每次选一个权最小的边吗？我的思考是相当与把一个正常的图每个边都减去一个同样大的值不是为负了吗？
2.用迪杰斯特拉算法求每一对顶点间的最短路径算法时间复杂度是O（n3）吗？因为求指定两顶点是O（n2），为什么有的书上说不对呢？

Answer 1

对于第一个问题： 权值一般代表一个抽象出来的路径长度，你想想既然是长度会是负数吗，如果你硬要说有，其实也无妨，“一个正常的图每个边都减去一个同样大的值不是为负了吗？”，这种做法并不影响程序的运行，只是失去了一些实际上的意义而已 第二个问题：迪杰斯特拉算法在求1：从一个源点到其他结点的最短路径时时间复杂度是O（n2），2：求每一对顶点间的最短路径其实就是多套一层for循环，这是当然是O（n3）了啊，这时和Floyd算法复杂度一样 5555回答完了哦