部分所有对最短路径
给定一个包含许多节点的无向加权图，如何计算所有对最短路径的子集？
子集是指图中的一些节点，而不是全部节点（图的顶点子集可以手动指定，也可以通过某种聚类算法指定。所选顶点的数量可能占总顶点的1%~5%）。
Dijkstra或Floyd Warshall可能会计算额外的节点，这对于我的应用程序来说可能不够有效。
是否有算法可以计算出特定节点之间的所有对最短路径并获得良好的性能？
共有1个答案
基本上，我认为你不能只考虑一些节点，因为子图中的最短路径可能不是全局最短的。所以你必须考虑所有的节点。
也许你可以这样实现Dijkstra的算法：在每次迭代中设置一个检查子程序。如果所有需要的节点都已经固定（已经找到最小路径）终止算法。这将为其余节点节省时间。
为了提高效率，如果没有负边缘长度，我建议使用n倍Dijkstra算法。如果有，使用约翰逊算法，它提供了一种特殊的重加权技术，将负边缘长度转换为非负边缘长度。
也许你只需要一台更快的服务器。
希望有帮助。
-
我已经成功地实现了Bellman-Ford，当边具有负权重/距离时，找到最短路径的距离。我无法让它返回所有最短路径（当最短路径有联系时）。我设法用Dijkstra获得所有最短的路径（给定的一对节点之间）。贝尔曼-福特有可能吗？（只是想知道我是否在浪费时间）
-
本文向大家介绍访问C ++中所有节点的最短路径，包括了访问C ++中所有节点的最短路径的使用技巧和注意事项，需要的朋友参考一下 假设我们有一个带有N个节点的无向连通图，这些节点被标记为0、1、2，...，N-1。图的长度将为N，并且仅当节点i和j连接时，j才与列表graph [i]中的i不完全相同。我们必须找到访问每个节点的最短路径的长度。我们可以在任何节点处开始和停止，可以多次访问节点，并且可以
-
我最近一直在研究所有成对最短路径算法，比如Floyd Warshall和Johnson的算法，我注意到这些算法即使在图包含负权重边（但不是负权重圈）时也能产生正确的解。相比之下，Dijkstra的算法（单源最短路径）不适用于负权重边。是什么让全对最短路径算法在负权重下工作？
-
我有一个加权和无向图，有顶点。其中两个顶点是和。 我需要找到最短的路径，从开始，在结束，并通过G的所有顶点（以任何顺序）。 如何做到这一点？ 这不是旅行推销员问题：我不需要访问每个顶点一次，也不想回到第一个顶点。
-
主要内容：最短路径算法在给定的图存储结构中，从某一顶点到另一个顶点所经过的多条边称为 路径。 图 1 图存储结构 例如在图 1 所示的图结构中，从顶点 A 到 B 的路径有多条，包括 A-B、A-C-B 和 A-D-B。当我们给图中的每条边赋予相应的权值后，就可以从众多路径中找出总权值最小的一条，这条路径就称为 最短路径。 图 2 无向带权图 以图 2 为例，从顶点 A 到 B 的路径有 3 条，它们各自的总权值是：
-
我试图解决的问题是： 给出一个图，其中每个边都用红色或蓝色着色： a）给出了生成两顶点(s，t)之间经过最小数量红边的路径的算法。