complex-networks - 复杂网络——找到一对节点之间所有可能的最短路径

Question

我有一个描述巨大网络的数据库。它由大约 18000 个顶点组成。现在我需要找到一对节点之间所有可能的最短路径。我已经尝试实现迭代 DFS，但问题是指数增长。所需的时间量变得巨大，因为顶点具有高出度。你能建议一些工作更快的算法吗？我拥有的复杂网络是定向和加权的。任何建议都会有很大帮助。

谢谢，埃克塔

score 0 · Accepted Answer

对于具有正权重的加权图，通常使用统一成本搜索，即Dijkstra 算法。在特定情况下，其他算法可能更快。例如，如果您的数据允许您定义启发式函数，则可以改用A*。或者，如果您的网络是无标度的（即它的度数是幂律分布的），您可以使用Peng 等人 12中描述的 Dijkstra 算法的变体。

编辑：要查找给定节点对之间的所有最短路径，您仍然可以使用 Dijkstra，并进行一些更改：

使用搜索树来应用算法（与直接基于您探索的图形应用算法相反）。这样，您可以轻松地表示通向同一节点的多条路径。请参阅WP 广度优先搜索文章以查看搜索树的示例。所以这更多是数据结构的问题。
允许再次访问已经访问过的节点，前提是 1) 通向该节点的路径与树中已经表示的路径不同，并且 2) 不比现有路径长。就搜索树而言，这意味着允许将一个图节点表示为两个不同的树节点，每个节点位于不同的分支中。
开发树直到找到第一个最佳解决方案，然后使用该解决方案的长度作为限制继续开发树（即，当分支达到此长度时停止开发）。
最后，每个包含目标节点的分支都应该对应一个最优的最短路径。

1 回答 1