Question

最短路径问题的复杂度是如何计算的？

Answer 1

v1到v2：10为最短路径；

v1到v3：7为最短路径；

v1到v4：8为最短路径；

v1到v5：v1-> v2 -> v5 =10+6= 16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15为最短路径；

v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13为最短路径；

v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；

v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35为最短路径

Dijkstra：

求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。

以上内容参考：百度百科-最短路径算法