最短路树和最短路 DAG

· · 个人记录

最短路树

最短路树是原图的一棵生成树，通常以起点 s 为根。

对于任意点 x，树上 s 到 x 的距离等于 s 到 x 的最短路。

建树：求最短路的过程中，若点 x 最后一次被边 (x,y) 松弛，则保留边 (x,y)。

习题：CF545E Paths and Trees

最短路 DAG

对于任意 x，最短路 DAG 中包含所有 s 到 x 最短路经过的边。

性质：

1.最短路 DAG 是有向无环图。若存在环，则原图中存在负环或 0 权环，此时不存在最短路 DAG。

2.最短路 DAG 的每一棵生成树都是最短路树，所有最短路树都是最短路 DAG 的生成树。

建图：求出最短路后，对于边 (x,y)，若 d_x+len_{(x,y)}=d_y，则保留这条边。

习题：

CF1005F Berland and the Shortest Paths（利用性质 2 求出所有所有最短路树）

P2149 [SDOI2009]Elaxia的路线（最短路 DAG 上拓扑求最长链）

CF1163F Indecisive Taxi Fee（断边最短路） 题解