最短路径的Dijkstra 改进算法，改进时间复杂度为O(n)有源代码吗？

Question

算法步骤为:
(1)计算s j 的直线距离k =s j , 若s j 之间存在1 条边, 则该边为最短路径, 若s j 上存在1 条边链即s j 由在一个方向的几条路段组成, 则该边链和为最短路径, 并记录该链所经过的站点及总距离, 否则, 执行步骤(2)。
(2)分别从s 、j 出发, 寻找与s j 、j s夹角最小的边, 设该边的另一端点分别为A1 和B1 即
|f (sj , sA1)|=min(|f (sj , sAi)|)
i∈D1
其中,D1 为所有与s 相连的节点数;
|f (js , jB1)|=min(|f (js , jBi)|)
i∈D2
其中,D2 为所有与t 相连的节点数。如果A1 是从s 出发所选的点, 则把A1 当作当前点, 用该步骤寻找以A1 为起点且与A1 j直线夹角的最小的边, 如此反复直至当前所选的点与j 点重合, 这样得到的一个链为最短路径的一个解。当所选点为终止点并该点与j 不重合时, 则这一条链到此结束, 然后把所选点的前一个点当作当前点继续执行该步骤, 如此循环。同样, 对于从j 出发的另一条链来说和从s出发的算法一样。这样sj 之间的最短路径的最终结果可能有2 条、1 条, 并记录该链所经过的站点以及阻抗值。该步骤所得的最短路径具有sj 两点的方向性趋势, 但其条件简单因此需进一步检验。
(3)同样以s 、j 分别为根结点, 然后分别用二叉树从s 、j 出发, 重复将s 、j 直线段两侧夹角最小的边加入二叉树, 对该二叉树的活动节点作2 个标记, 直至与j 或s 点重合。这样sj 之间的最短路径最多有4 条结果。为了减少花费时间并使构造的二叉树最小, 应采用两种方法:首先对于二叉树的遍历采用广度优先的方法, 尽可能减少二叉树的节点遍历数;其次对于子结点在加入路径队列前, 对其进行判断, 如果为终点j(s), 则不加入路径队列, 但要对其影响的节点和子节点累加长度标志进行改变。

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 请看👉 ：[C]可视化的Dijkstra标号算法求带权图的最短路径和距离

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 以帮助更多的人 ^-^