关于最短路径算法在业务情景中实现的改进，与技术选型决策探讨

Question

背景介绍 业务模型： 有这么一个场景。数据库中存储了一些点元素【A,B,C...,Z】以及构建与点元素之上的线元素【AB,BC,...，YZ】。 比较特别的一点是，计算最短路径时，两点之间的线段只有满足某些特定要求（随请求传入）的时候才算做可达，可达的线元素权重均为1。 需求 任意选择两个网元，规定好特定需求，然后找出其中满足特定需求且跳数最少的线列表作为最短路径。 目前的解决办法 采用 Dijkstra 算法，根据使用场景做了个变种，可达路径的权值均设为1。 过程分为两个步骤， 从起始点开始，检索相关联的线段。 依据特定需求排除掉不可达线段，缓存起来。 将可达线段的另一端点作为下一跳起始点，重复1，2步骤。 找到第一次找到终点时终止。 由于该特定需求的可达判定需要动态的进行数据库查询，所以为了减小过程中的网络开销，第一版代码是由前人用存储过程写在数据库的执行的。这也导致了如下几个显著的缺点： 维护成本高昂，这个算法的主体写了小1k行（其他支持性函数加起来另外有1k行），任何后来人对这个算法做任何改动，都得先花几天时间对存过逻辑进行梳理。（这点其实有更深层次的原因，相较java，存过更不容易拥有良好的封装，所以coder们稍不自觉，业务逻辑和算法主体也就紧紧的耦合在一起了） 难以拓展，业务中相似的最短路径搜索需求其实挺多的，但是因为算法方案与特定需求的可达判定耦合比较紧密，所以每类需求的实现都有不同程度的重复代码，当经历了不同人的几轮维护之后，到我手中每处重复的代码都总有微小的不同，重构难度较大。 计算速度偏慢，客户反馈过多次，跳数较多的情况下计算偏慢。其实也好理解，遍历过程中总有些核心点与多个点有线段链接，只要查询过程多经过几个核心节点，计算量都是爆炸。 可能的改造思路 改造思路 宏观来说，将主体算法移植进代码层并考虑替换掉 Dijkstra 算法 细节来说，逻辑上采用模板方法模式对算法主体进行封装，暴露出遍历下一跳的以及可达判定方法作为钩子方法。以完成算法主体逻辑与业务细节的解耦合。 面临的问题： 算法不熟：因为我对图论相关算法并不熟悉（其实别的算法积累也比较薄弱），所以目前并不知道什么样的算法更加适合这个可达权值均为1的场景，不知道有没有过来人能给点建议？ 网络开销：将算法主体移植到代码层，固然提升了功能的可维护性以及可拓展性，但是由于查找下一跳以及判断是否可达，都需要动态查询。在原有算法思路下，过程中必然伴随着大量 sql 读请求的出现，相较于之前放在存储过程中，网络开销的增加也不可忽视，所以我很懵逼，有什么办法可以优化掉这层网络开销吗？建表进行数据缓存是一种可行的思路吗？ 这个问题是在日常工作中，自己觉得还是挺典型的一类问题，它的解与算法有关又不局限与算法，还涉及了代码或者数据库层面的选型。作为一个新手，难免有自己的知识盲点，所以想拿出来与大家做一些探讨，如果社区大大们有什么好的建议，不论是您看过相关算法好的文章链接，还是关于代码解耦或者提效有什么好的建议/经验，还望不吝赐教，碰到好的回答我会及时采纳的

Answer 1

换个角度看下你的问题。

1. 既然现在的地图app都是毫秒级返回，那么计算肯定不是在请求后才进行（或部分进行），那必然有缓存。

2. 理论上点构成线，是点的全排列，但可以排除很多无用的线，比如不可达（不认为有现实意义的不可达，应该算代价大小）

举例：程序运行一年后，发现某地区计算最多的是道路C-A-I，Y-O-N-G，J-I，那这部分可以缓存起来。现实中想去某个地方，你脑海里不会有太多“路的走法”，也就是说每单次请求并没有太多元素需要计算，更谈不上全排列。

如果我来设计，我会多设计一个概念“优先级”，来将地点/线路等概念（元素）进行区别对待。

假设一座城市有Pa-Pz主要地点，P1-P10000次要地点。
Ra-Rz主要道路，R1-R10000次要道路。
缓存Pa-Pz间全排列路径（地点间走法）。
缓存Ra-Rz间所有途径点，记录距离，权重等信息。
计算任意地点间路径逻辑：

1. 计算地点A到主要地点路径，走法。

2. 计算地点B到主要地点路径，走法。

3. 连通，得到n条路径（点序列）。

以上是初步结果，再对结果进行纠正（条件导入）：

1. 遍历点序列，并跟据单点辐射范围道路，进行最短路径优化选择。

2. 将其缓存或计入日志方便日后统计。

Answer 2

对于一个边权重都为1的图，不用dijkstra吧。这里不是用简单的广搜就可以解决了么。

Answer 3

Dijkstra 可以做到N*logN的.请用堆进行优化.
或者可以尝试考虑SPFA,

Answer 4

如果算法不行又不想学算法，想代码写的少有具有扩展性，但是对于效率不是要求那么高，或者不要求最优解只需要近似最优解，那么推荐你用Optaplanner，

Answer 5

【建议】

这个问题我没看懂，但是从算法角度提出几个建议，方便LZ更快地找到答案：

数据库中存储了一些点元素【A,B,C...,Z】以及构建与点元素之上的线元素【AB,BC,...，YZ】

可否说下数据量，点元素数据量，边的数据量，以及数据量的在大小极值之间的分布。抱歉，我是刷oj刷多了，所以。。。。。。因为算法是建立在 “问题 + 数据” 之上的。

Answer 6

2017年6月19日补充

虽然解空间的边元素一开始就存在了，但对于用户的一个特定的最短路径请求而言，这其实是个伪边，因为还要满足与起止节点一起传过来的特定约束才能算作解空间的候选边。

又考虑到满足约束即算可达，所有候选边权重均为1，所以实际上这里的Dijkstra算法就简化成了一个边元素需要动态计算的图的广度优先遍历问题。

不知道我这样简化问题逻辑是不是有盲点？是不是还有比广度优先更简单的解法呢？

另：实际业务场景中的点元素大概在1万~10万左右，放在代码内存中有点担心内存爆炸。。。