用户维护好仓区的点和线,生成分布图时,用户任意选取两个点,后端求出当前最短路径。
假设图G(m, n),m个顶点,n条边
算法对比:
- floyd算法
时间复杂度o(m3)
缺点:时间复杂度过高 - dijkstra算法
时间复杂度o(m2),使用优先队列可以降到o(m * logm)
邻接矩阵存储:适合稠密图
邻接表存储:适合稀疏图
缺点:不适合负权场景
项目业务场景不存在边为负权,并且大部分为稀疏图,所以采用dijkstra算法,使用邻接表存储各个节点离初始点的最短距离,通过给点增加前置节点属性保存最短路径轨迹
使用优先队列对比测试(空间换时间)
图G(7,10)
代码预热后测试(类加载是按需加载,第一次跑会进行类加载过程,会消耗较多时间,所以先空跑两次预热后再进行时间的统计):
调用次数 | 10 | 1000 | 2000 |
优化前消耗时间 | 1ms | 28ms | 35ms |
优化后消耗时间 | <1ms | 12ms | 15ms |