有向非负权图中经过必经节点集最短路径算法

传统的Dijkstra算法只是针对起点和终点求解最短路径,而不能解决从起点出发,经过必经节点集,到达终点的无重复节点且无回路的最短路径问题。为此,在有向非负权图中,提出了Dijkstra算法和回溯法相结合的方法。对Dijkstra算法改进,并求解关键节点(起点,终点和必经节点)间的最短路径,进而从关键节点所构成的矩阵中采用回溯法得到目标路径。通过实际的算法实现,测试大量的有向非负权图数据,证实了算法的有效性和正确性。

必经节点集约束型无环最短路径算法研究

基于遗传算法和Dijkstra算法,提出了解决必经点集约束型无环最短路径问题的方法.将研究问题分解为只含源点、目的节点和必经节点集的非对称旅行商问题和消除环路问题.首先利用遗传算法求解非对称旅行商问题得到最优必经点序列.但求解得到的最优必经点序列组成的路径是有环路径,为解决环路问题,设计了分段Dijkstra破环策略.通过实验分析验证了算法是有效可行的,相对于传统方法,在时间效率上有较大的提升.