论文部分内容阅读
提出了求图中一个顶点到另一个顶点的受顶点数限制的所有最短路径的一个算法。该算法利用稍加扩展的Dijkstra算法求出终点到其它相关顶点的受顶点数限制的最短路径的长度，然后根据这些数据用回溯法找出源点到终点的受顶点数限制的所有最短路径。记起点到终点的中间点数不超过k的最短路径有e条，图中共有w条边，则算法的时间复杂度为O（w＋nlog2n＋kw＋ew）。实验结果表明实际的运行时间与图的结构：行很大关系。