什么是制作另一个具有顶点的图的方法，该顶点只能从V原始未加权（假设长度为 1）和无向图中的每个顶点的边长度为 l 得到G=(V,E)。我想出了一个解决方案，它只V在每个顶点上使用深度优先搜索从每个分支中搜索每个分支，直到找到每个顶点的路径长度为 l 的所有顶点。当然，这提供了一个运行时间O(V^(l+1))，这不是最佳解决方案。谁能帮助我找到具有更好渐近运行时的更好解决方案？
问问题
97 次
1 回答
0
您可以使用Floyd-Warshall算法，该算法使用矩阵表示（如@Hammar 建议的那样），但O(V^3)无论l. l您可以通过顺序插入节点并确定对最短路径的影响来确定所有距离，而不是矩阵求幂。
于 2012-11-11T09:46:35.710 回答