复杂网络——寻找一对节点之间所有可能的最短路径
Complex Networks-Finding all possible shortest paths between a pair of nodes
我有一个描述庞大网络的数据库。它由大约18000个顶点组成。现在我需要找到一对节点之间所有可能的最短路径。我已经尝试实施迭代 DFS，但问题是指数 growth.The 所需的时间量变得巨大，因为顶点的出度很高。你能推荐一些运行速度更快的算法吗？我拥有的复杂网络是定向的，weighted.Any 的建议会很有帮助。
谢谢，
埃克塔
对于具有正权重的加权图，通常使用统一成本搜索，又名 Dijkstra's algorithm. Other algorithms can be faster in specific cases. For example, if your data allow you to define a heuristic function, you could use A* instead. Or if your network is scale-free (i.e. its degree is power law distributed), you can use a variant of Dijkstra's algorithm described in Peng et al.'12。
还有一堆相关的 SO 问题你可能想看看，比如 Is there better way than a Dijkstra algorithm for finding fastest path that do not exceed specified cost or Are there faster algorithms than Dijkstra?。
编辑：要查找给定节点对之间的所有最短路径，您仍然可以使用 Dijkstra，并进行一些更改：
- 使用搜索树来应用算法（反对直接基于您探索的图来应用算法）。这样，您可以轻松地表示通向同一节点的多条路径。请参阅 WP Breadth-first search article 以查看搜索树的示例。所以这更多是数据结构的问题。
- 允许再次访问已经访问过的节点，前提是 1) 通往该节点的路径与树中已经表示的路径不同，并且 2) 不长于现有路径。在搜索树方面，这意味着允许一个图节点表示为两个不同的树节点，每个树节点在不同的分支中。
- 开发树，直到找到第一个最优解，然后以这个解的长度为限继续开发树（即当分支达到这个长度时停止开发树）。
- 最终，每个包含目标节点的分支都应该对应一条最优的最短路径。
你也可以看看这个问题（虽然是未加权图）：Finding all the shortest paths between two nodes in unweighted undirected graph
我有一个描述庞大网络的数据库。它由大约18000个顶点组成。现在我需要找到一对节点之间所有可能的最短路径。我已经尝试实施迭代 DFS，但问题是指数 growth.The 所需的时间量变得巨大，因为顶点的出度很高。你能推荐一些运行速度更快的算法吗？我拥有的复杂网络是定向的，weighted.Any 的建议会很有帮助。
谢谢， 埃克塔
对于具有正权重的加权图，通常使用统一成本搜索，又名 Dijkstra's algorithm. Other algorithms can be faster in specific cases. For example, if your data allow you to define a heuristic function, you could use A* instead. Or if your network is scale-free (i.e. its degree is power law distributed), you can use a variant of Dijkstra's algorithm described in Peng et al.'12。
还有一堆相关的 SO 问题你可能想看看，比如 Is there better way than a Dijkstra algorithm for finding fastest path that do not exceed specified cost or Are there faster algorithms than Dijkstra?。
编辑：要查找给定节点对之间的所有最短路径，您仍然可以使用 Dijkstra，并进行一些更改：
- 使用搜索树来应用算法（反对直接基于您探索的图来应用算法）。这样，您可以轻松地表示通向同一节点的多条路径。请参阅 WP Breadth-first search article 以查看搜索树的示例。所以这更多是数据结构的问题。
- 允许再次访问已经访问过的节点，前提是 1) 通往该节点的路径与树中已经表示的路径不同，并且 2) 不长于现有路径。在搜索树方面，这意味着允许一个图节点表示为两个不同的树节点，每个树节点在不同的分支中。
- 开发树，直到找到第一个最优解，然后以这个解的长度为限继续开发树（即当分支达到这个长度时停止开发树）。
- 最终，每个包含目标节点的分支都应该对应一条最优的最短路径。
你也可以看看这个问题（虽然是未加权图）：Finding all the shortest paths between two nodes in unweighted undirected graph