Dijkstra算法问题求从某源点到其余各顶点的Dijkstra算法,当图的顶点数为10,用邻接矩阵表示图时计算时间约为10ms,则当图的顶点数为40时,计算时间为多少ms?请写出具体分析,谢谢

分类: 作业答案 • 2022-08-07 20:36:27

问题描述：

Dijkstra算法问题
求从某源点到其余各顶点的Dijkstra算法,当图的顶点数为10,用邻接矩阵表示图时计算时间约为10ms,则当图的顶点数为40时,计算时间为多少ms?
请写出具体分析,谢谢

答

dijkstra算法的时间复杂度是O(n²),
不妨设为kn²,其中次数小于1的项忽略
k(10×10）=10ms
那么k(40×40）=16[k×（10×10）]=160ms