Dijkstra算法问题
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/08/04 01:03:47
Dijkstra算法问题
求从某源点到其余各顶点的Dijkstra算法,当图的顶点数为10,用邻接矩阵表示图时计算时间约为10ms,则当图的顶点数为40时,计算时间为多少ms?
请写出具体分析,谢谢
求从某源点到其余各顶点的Dijkstra算法,当图的顶点数为10,用邻接矩阵表示图时计算时间约为10ms,则当图的顶点数为40时,计算时间为多少ms?
请写出具体分析,谢谢
![Dijkstra算法问题](/uploads/image/z/863967-39-7.jpg?t=Dijkstra%E7%AE%97%E6%B3%95%E9%97%AE%E9%A2%98)
dijkstra算法的时间复杂度是O(n²),
不妨设为kn²,其中次数小于1的项忽略
k(10×10)=10ms
那么k(40×40)=16[k×(10×10)]=160ms
不妨设为kn²,其中次数小于1的项忽略
k(10×10)=10ms
那么k(40×40)=16[k×(10×10)]=160ms