Dijkstra算法的运行时间？

有哪位大神知道：
用Dijkstra算法计算百级、千级、万级、百万级节点的平均搜索时间大概是多少？
我用我的算法测试了一下 300多顶点的图平均每对才1.9ms，是不是错了？
求各位指导。