使用JGraphT实现随机信标最短路径路由的相关技术问题

1. 随机信标选取方法 #

你可以直接利用JDK自带的集合工具实现无偏随机采样，步骤非常简单：

• 首先从JGraphT图实例中拿到全量顶点：List<V> allVertices = new ArrayList<>(graph.vertexSet());，把Set转成列表才能按索引随机访问
• 先做参数校验：如果p <= 0或者p > allVertices.size()，直接抛出非法参数异常，避免后续逻辑出错
• 调用Collections.shuffle(allVertices)打乱列表顺序，这个方法底层用的是Fisher-Yates洗牌算法，能保证所有顶点的采样概率完全均匀
• 如果需要固定随机种子复现实验结果，可以给shuffle方法传入自定义的Random实例：Collections.shuffle(allVertices, new Random(自定义种子数值));
• 取打乱后列表的前p个元素作为信标，存到Set<V> beacons = new HashSet<>(allVertices.subList(0, p));，后续判断某顶点是不是信标也能O(1)时间查询。

2. 信标全对最短路径存储方案 #

预计算的时候不用跑全图的Floyd算法，只需要对每个信标跑一次单源最短路径（比如Dijkstra）就可以，存储推荐两种适配不同场景的方案：

方案1：嵌套HashMap存储（通用场景首选） #

这种方案不需要额外做索引映射，适配任意顶点类型，使用最方便：

• 如果只需要存储最短路径长度：定义Map<V, Map<V, Double>> beaconDistanceMap，查询两个信标b1、b2的路径长度直接调用beaconDistanceMap.get(b1).get(b2)即可，时间复杂度O(1)
• 如果需要存储完整路径信息：定义Map<V, Map<V, GraphPath<V, E>>> beaconPathMap，值直接存JGraphT原生的GraphPath对象，需要取路径边、路径顶点或者路径权重都可以直接调用对应方法获取。

方案2：索引映射数组存储（信标数量较大时首选） #

如果信标数量p在几百以上，嵌套HashMap的空间开销会更高，这时候可以用数组存储进一步提升性能：

• 先给每个信标分配唯一的整型索引，构建映射关系：Map<V, Integer> beaconToIndex = new HashMap<>(); 遍历信标集合依次赋值0到p-1的索引
• 路径长度用二维数组存储：double[][] distanceMatrix = new double[p][p];，完整路径用二维数组存储：GraphPath<V, E>[][] pathMatrix = new GraphPath[p][p];
• 查询的时候先通过映射拿到信标的索引，再访问数组对应位置即可，查询效率比HashMap更高。

内容的提问来源于stack exchange，提问作者deansjam