-1

给定一个加权图,当前我有超过 100 个节点。那么问题是如何通过属于构建图的节点数组(实例为 10 个节点)找到最短路径。这个问题似乎类似于旅行商问题,但事实并非如此。

我当前的解决方案非常简单 第 1 步:从 10 个节点的数组构建一个新图,我必须从第 2 步构建游览:使用 Dijkstra 查找节点之间的距离并连接图中的所有顶点 第 3 步:现在它只是转旅行商问题

简单的。但是,第 2 步的复杂度是 O(n^2),因为我必须为新图的所有节点组合找到最短路径(Dijkstra 具有多项式复杂度)。

如何让我的算法更快?最好的情况是我可以消除必须为新图中的每对节点组合找到最短距离的瓶颈。

4

1 回答 1

1

Dijkstra的复杂度为 O(E log(N)),如果你有完整的图(如果你正在做 TSP,你有),那么对于所有节点对,你可以将其写为 O(N² log(N))它是 O(N⁴ log(N))。因此,使用Floyd-Warshall 算法应该更有效,该算法在 O(N³) 中的所有节点对中找到最短路径。

于 2013-03-29T12:35:23.773 回答