求单源最短路径的新方法

参见：dijkstra 算法为什么高效。

本来不想谈算法，本来只想了一下 dijkstra 算法背后的形而上，但还是归纳出一个仅靠一次广度优先遍历就能获得单源最短路径的新算法，框图里是算法流程，流程下是一个例子：

它不单单可在广度优先遍历时间复杂度求解最短路径，还能在支付额外的 insert 时间后求出所有第 2 短，第 3 短，第 4 第 5 第 n 短路径，非常高尚。

啊哈，真的有这么简单吗，我的感觉怪怪的，总觉得哪里少了一步，O(n^2) 基础时间复杂度是少不了的，因为至少要比较两个维度，剩下的优化另说，至多收到 log。确实，这段是我后来增加的，外出散步时想到了问题点。

注意上图，S–A 在被 S–F–A 接管后，纵坐标下移了三层，图虽然画对了，但在算法步骤里并没有标识清楚这三层下降带来的附加操作：

新的最短路径节点接管老最短路径节点的所有孩子节点，并带来这些孩子节点纵坐标下降三层，以此递归操作，如果孩子节点有不同的父节点，则保留原父结点指向，分裂孩子节点下降三层。

这下就补上了遗漏的时间复杂度，但为什么是广度优先遍历，就是为了让递归不至于过深，事实上递归操作并非标称的时间复杂度，而大概率只有一到两次。换句话说，孩子节点将只从纵坐标最低处生出，广度优先遍历可让在递归孩子节点时，孩子代数不会过深，这就是这个算法的妙处。

补充图示如下(上图视作有错误的第一版，废弃)：

它来自于我惯常的横竖一颠倒的方法论，标准 dijkstra 算法的 “贪心” 体现在 V_c 纵坐标的冒泡，而 “松弛” 则体现在 V_c 纵坐标的求解。这算法没有任何松弛比较，而是无条件求出 V_c 纵坐标并将它标识在坐标系，这又体现了我惯常的数形结合方法论，坐标系里肉眼可见，无需任何奇技淫巧。

可能的数据结构如下：

struct node {
    // 保存指向该节点的 node list
    struct list_head from；
    // 保存该节点指向的 node list，便于广度优先遍历
    struct list_head to；
    // 保存该节点第 1 短，第 2 短，... 的 path list
    struct list_head path；
    uint curr_lowest_w;
    uint index；
 };
    
struct edge {
    struct node from；
    struct node to；
    uint weight；
}; 

struct path {
    struct list_head nodes;
};

那为什么 dijkstra 算法和我上述的算法都无法处理负权重边？

昨天的文字中提到，dijkstra 算法模拟的是 “自然发生的过程”，背后是第一性原理，负权重边恰恰是 “不可能自然发生的”。以爆炸为例，当冲击波接触到某处，冲击波袭来的路径一定最短，若希望冲击波以某种方式先接触到它处再拐回的速度更快，除非时间倒流，在自然尺度下这不可能发生，再以河水泛滥为例，洪水淹过某地，洪水经过的路径一定最短，若要洪水经过别处再拐回的路径更短，除非水往高处流，在自然重力下，这不可能发生。

本文到此为止，为日后检索不至于主体不明确而乱掉，不将不同主题放入一篇文字，另起一篇单独做一个携带负权重边的有向图建模，展示一下非自然的熵减过程如何产生负权重边。

浙江温州皮鞋湿，下雨进水不会胖。