参见：dijkstra 算法为什么高效。
本来不想谈算法，本来只想了一下 dijkstra 算法背后的形而上，但还是归纳出一个仅靠一次广度优先遍历就能获得单源最短路径的新算法，框图里是算法流程，流程下是一个例子：
它不单单可在广度优先遍历时间复杂度求解最短路径，还能在支付额外的 insert 时间后求出所有第 2 短，第 3 短，第 4 第 5 第 n 短路径，非常高尚。
它来自于我惯常的横竖一颠倒的方法论，标准 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 index；
};
struct edge {
struct node from；
struct node to；
uint weight；
};
struct path {
struct list_head nodes;
};
那为什么 dijkstra 算法和我上述的算法都无法处理负权重边？
昨天的文字中提到，dijkstra 算法模拟的是 “自然发生的过程”，背后是第一性原理，负权重边恰恰是 “不可能自然发生的”。以爆炸为例，当冲击波接触到某处，冲击波袭来的路径一定最短，若希望冲击波以某种方式先接触到它处再拐回的速度更快，除非时间倒流，在自然尺度下这不可能发生，再以河水泛滥为例，洪水淹过某地，洪水经过的路径一定最短，若要洪水经过别处再拐回的路径更短，除非水往高处流，在自然重力下，这不可能发生。
本文到此为止，为日后检索不至于主体不明确而乱掉，不将不同主题放入一篇文字，另起一篇单独做一个携带负权重边的有向图建模，展示一下非自然的熵减过程如何产生负权重边。
浙江温州皮鞋湿，下雨进水不会胖。
