问题：我有大量的积分。这些点中的每一个都有一个列表，其中包含对其他点的引用，它们之间的距离已经计算和存储。我需要确定从起点开始并通过特定数量的点到达任何目的地的最短路线。
例如：我正在度假，我住在一个特定的城市。我正在做一次单程旅行，去参观任何四个城市，我想尽可能地走最短的距离。我不能多次访问同一个城市。
当前解决方案：现在我只是手动迭代所有可能性并存储最短路径。这有效，但感觉效率低下。此外，这个问题最终会扩展到包括从多个起点到多个目的地的搜索，所以我认为这可能会扩大搜索空间。
搜索最短路线的更好方法是什么？
回答更新后的帖子，您检查每种可能性的解决方案是最佳的（至少，到目前为止，没有人发现更好的算法）。是的，那是一个旅行推销员，他的本质不是每一座城市，而是每一座城市一次。如果您不想寻找可能的最佳解决方案，您可能会发现使用更快的启发式算法很有用，但允许与理想解决方案之间存在有限的差异。
对于未来的回答者：Floyd-Warshall 算法和所有类似 Floyd 的变体在这里都不适用。
一般来说，你应该严格错误的变体......我认为你应该使用 Branch_and_bound 方法的一些变体 http://en.wikipedia.org/wiki/Branch_and_bound
像norheim.se所说的bredth first search或Dijkstra的算法也是我的建议。
这听起来像旅行推销员？一种解决方案是使用优化技术，例如进化算法。目前你正在做一个详尽的搜索，它会很快变得非常慢。但我认为这几乎是一个旅行推销员问题，它已经解决了几十年甚至几个世纪，因此有几种可能的攻击方式。谷歌是你的朋友。
也许这就是原始海报通过“手动迭代每种可能性并存储最短路径”的意思，但我想我想明确什么似乎是基线解决方案。
假设你已经有一个两点最短路径算法——这有各种图形的经典解决方案。假设所有距离都是非负的并且 d(A->B->C) = d(A->B) + d(B->C)。
要点是从 S 开始的路径经过中间城市“abcd”之一并以 E 结束：
例如 SabcdE、SacbdE 等...
只有 4 个中间城市，您可以枚举所有 24 个排列。对于每个排列，使用最短的两点算法来计算从头到尾的路径及其总距离。
然后给定起点和终点，有 12 种可能性附加到 abcd 之一，并且对于内部的每两种可能性。您已经计算了这些距离，因此您添加了从 S 到头部的距离和从尾部到 E 的距离。选择最小值。因此，一旦您预先计算了一组固定的内陆城市的中间距离，您就需要为任何一对起点和终点做 12 个两点最短路径问题。
随着中间城市数量的增加，这显然无法扩展。我不清楚它是否可以做得更好，除非您对图结构施加更大的限制（这是在物理欧几里得空间中吗？三角不等式？）。
我的思想示例：假设城市之间的所有中间距离都是 O(1)。对图没有限制，那么从 S 到任何中间城市的距离可能是 1000，除了一个是 1。尾巴也是如此。所以你可以强制第一个被访问的城市是任何东西。现在，往下一层，以第一个城市为“起点”。应用相同的论点：您可以通过操纵图中的距离使最佳路径前往以下任何城市。
因此，如果没有额外的假设，似乎无法帮助复杂性。
这是任何人都可能陷入的非常常见和实时的情况。谷歌地图用户界面以相同的顺序为您提供路径，您添加到目的地列表中。尽管他们自己的 Google 地图 API 提供了解决方案，但它并没有为您提供最佳路径。
谷歌地图API为此提供了解决方案。在查找路径的请求中，您必须提供标志“optimizeWaypoints：true”。请求看起来像这样。
var request = {
origin: start,
destination: end,
waypoints: waypts,
optimizeWaypoints: true,
travelMode: google.maps.TravelMode.DRIVING
};
您可以在查看源代码中看到该实用程序的完整代码，因为完整的实用程序是用 javascript 和 HTML 开发的。
我希望它会有所帮助。
您的图表的边缘似乎是双向的。在这种情况下，您要查找的算法是Dijkstra 算法。