什么是制作另一个图形的方法，该图形的特征是只能从原始未加权（假设边长度为1）和无向图 G=(V,E) 的每个顶点 V 获得边长为l的顶点 . 我想出了一个解决方案，它只使用每个顶点上的深度优先搜索来搜索每个分支中的每个分支，直到找到每个顶点的路径长度为l的所有顶点 . 这给出了 O(V^(l+1)) 的运行时间，所以当然，这不是最佳解决方案 . 任何人都可以帮助我找到一个更好的渐近运行时更好的解决方案吗？
G=(V,E)
V
O(V^(l+1))
您可以使用使用矩阵表示的Floyd-Warshall算法（如@Hammar建议的那样），但在 O(V^3) 中完成，而不管 l . 您可以通过顺序插入节点并确定最短路径上的效果来确定所有距离，而不是 l 矩阵指数 .
O(V^3)
l
1 回答
您可以使用使用矩阵表示的Floyd-Warshall算法（如@Hammar建议的那样），但在
O(V^3)中完成，而不管l. 您可以通过顺序插入节点并确定最短路径上的效果来确定所有距离，而不是l矩阵指数 .