带负权有向无环图的最短路径

Posted on Mon 15 May 2017 in Computer

最短路径

正权图

用广度优先,先到达的点一定是最短路径。因此不需要考虑后续更新问题

带负权

由于先到达的某条路可能被后面带负权的路所代替,需要考虑后续更新问题。为了防止某节点的最短路径更新导致的后续步骤重算,任何节点必须等待他的依赖做完,此时给出的路径才是真正的最短路径。这个过程需要使用拓扑排序(考虑依赖的任务排序)来实现。

每次某个事情做完的时候,计算假设走该路径它的后继到达所需要的时间。如果该时间更短的话,给它的后继节点更新时间并记录该路径。

拓扑排序

初始时有一系列任务待处理,构成一个任务树。这些任务有的不需要依赖(入度为零)即可以完成,称为树叶;另一些是出度为零的树根;其他的称为树干。每次剪除任意一个枝叶,此次剪除可能产生新的枝叶,加入枝叶队列。以此不断循环。

此方法应用于一个任意有向/无向图可以剪除所有树枝,剩余的皆是非平凡的,或者连接环路的