最短路径算法大讨论2！100百万个点规模10秒！

续上一期话题，欢迎大家继续讨论。小弟再次还有几个问题需要高手指点一二！
1、对于无向图来讲，边的个数是怎么算的？比如包含10条边的无向图，在算法中实际要存储的是20条边，这种情况下可以说网络中是包含20条边的规模吗？
2、五万个点，76182条边的无向图，运行平均0.5秒，算快吗？
3、10万个点、20万条边的无向图，运行平均1.5秒，算快吗？
4、100百万个点、400百万条边规模的有向图，运行平均16秒左右，算快吗？


注：上述中的无向图中的边数均为实际网络中的边数，算法中存储的边数为上述数字的2倍。

补充一个问题，对于百万级别的网络，正常的dijkstra算法（不经优化的）运行时间在什么量级？其它不经优化的最短路径算法又是在什么量级？

没用这么大的数据量测试过

1、对于无向图来讲，边的个数是怎么算的？比如包含10条边的无向图，在算法中实际要存储的是20条边，这种情况下可以说网络中是包含20条边的规模吗？

复杂度的意义上没区别。实际上要说20条边也可以。

2、五万个点，76182条边的无向图，运行平均0.5秒，算快吗？
3、10万个点、20万条边的无向图，运行平均1.5秒，算快吗？
4、100百万个点、400百万条边规模的有向图，运行平均16秒左右，算快吗？

显然慢。这种稀疏图显然用E*logV的算法能在400w边的时候依然1秒以内。

>对于百万级别的网络，正常的dijkstra算法（不经优化的）运行时间在什么量级？
稀疏图一定要用V^2的dijkstra那是自己算法的选择失误，运行有多慢没人关心。其他算法的话大概spfa可能会对随机数据也能达到E*logV的dijkstra的速度