消除路由图中未在节点子集之间的最短路径中使用的边

Question

我有一个大型无向铁路路线图，其中有数百万个节点，每个节点的邻居数量都很少。我使用图表在几千个终端之间进行路由，并且我想减少图表所需的内存，不影响任何终端之间的最短路径。我知道图中的很多边不会位于任何一对终端之间的最短路径上（可能是 50%，可能是 95%，我不知道）。

如何找到并消除尽可能多的无用边缘（和/或节点），但又与计算要求保持平衡？

我对完美的解决方案感兴趣，但我更喜欢用 50% 的资源获得 90% 的完美解决方案。

我一直在考虑的一些想法：

完美解决方案

使用最短路径算法 (Dijkstra / A*) 查找每对之间的最短路径，消除任何这些路径中未使用的所有边。

这似乎会占用太多资源，不值得尝试。

谱聚类

我只读了一点相关内容，但似乎由于需要邻接矩阵而无法考虑，而邻接矩阵在

|V|^2

需要太多内存。

删除具有单边的节点

任何不是终端之一且只有一个邻居的节点都可以被删除，重复此过程确实会删除一大块，但我知道还有更多。

找到桥梁并在不需要时进行切割

我可以使用 Tarjan 算法来查找桥，每个桥连接 2 个子图。如果其中一个子图没有终结符，则可以将其删除。如果它只有几个终端，我可以在其中使用上面的完美解决方案（以及桥本身）。

我还没有尝试过这个，但我认为它会非常有效，但是 grpah 中仍然会有大量高度连接的部分，与图的其余部分有 2 或 3 个连接，无法通过此方法进行压缩。

将其扩展到双桥子图

我在某处读到，可以修改 Tarjan 的算法来检测与图的其余部分只有 2 个边的子图 - 看起来很直观，它可以工作，但我不完全了解它是如何工作的。

Answer 1

您没有确切地说，但我假设您想这样做，以便可以使有关两个航站楼之间路线的常规问题变得非常高效。

所以，这就是我解决这个问题的方法。

0.  Remove leaf nodes ( nodes with a single edge )
1.  A query comes in for the shortest path between two terminals in full graph Fg
2.  Find shortest path between terminals in Fg
3.  While waiting for next query
3.1     Create an empty graph Eg
3.2     Add terminals and shortest path ONLY to Eg
4.  A new query comes in for path between two terminals
5.  IF both terminals in Eg find path in Eg
6.  ELSE
6.1     Find shortest path between terminals in Fg
6.2     Add terminals and shortest path ONLY to Eg excluding links already in Eg
6.3     IF Eg contains all terminals, drop searching in Fg
7.  LOOP back to 4.