给定一个加权图，当前我有超过 100 个节点。那么问题是如何通过属于构建图的节点数组（实例为 10 个节点）找到最短路径。这个问题似乎类似于旅行商问题，但事实并非如此。
我当前的解决方案非常简单 第 1 步：从 10 个节点的数组构建一个新图，我必须从第 2 步构建游览：使用 Dijkstra 查找节点之间的距离并连接图中的所有顶点 第 3 步：现在它只是转旅行商问题
简单的。但是，第 2 步的复杂度是 O(n^2)，因为我必须为新图的所有节点组合找到最短路径（Dijkstra 具有多项式复杂度）。
如何让我的算法更快？最好的情况是我可以消除必须为新图中的每对节点组合找到最短距离的瓶颈。