连通节点图的快速路径缓存生成

我在为一个连通节点图工作的游戏中,试图获得一个更快的寻路机制。节点分为两类,“网络”和“路由器”

在这张图中,蓝色的圆圈代表路由器和灰色的矩形网络。

每个网络都有一个它连接到哪些路由器的列表,反之亦然。路由器不能直接连接到其他路由器,网络也不能直接连接到其他网络。

网络列出它们连接到的路由器



路由器也这样做

我需要得到一个算法,它将为每个可能的源和目标网络绘制出一条路径,以交叉网络的数量来衡量,不包括源和目标是同一网络的路径。我现在有一个,但是它非常慢,大约需要两秒钟来绘制路径,这对于所有连接的玩家来说都是非常明显的。

当前的算法是一种深度优先的暴力搜索(大约一个小时内就完成了这一搜索,以使路径缓存正常工作),它按网络遍历的顺序返回一个网络数组,这就解释了为什么它如此缓慢。有没有更有效的算法?

作为旁注,虽然这些示例图有四个网络,但实际中的图有55个网络和大约20个正在使用的路由器。不可能的路径也会发生,并且在任何时候网络/路由器图的拓扑结构都会发生变化,需要重建路径缓存。