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