草庐IT

DijkstraVertex

全部标签

c++ - Dijkstra 算法实现的性能

下面是我根据Wikipediaarticle中的伪代码编写的Dijkstra算法的实现。.对于具有大约40000个节点和80000条边的图,运行需要3或4分钟。这是正确的数量级吗?如果不是,我的实现有什么问题?structDijkstraVertex{intindex;vectoradj;vectorweights;doubledist;intprev;boolopt;DijkstraVertex(intvertexIndex,vectoradjacentVertices,vectoredgeWeights){index=vertexIndex;adj=adjacentVertices