ACM图论必备定理：最优子结构

算法与数据结构 7

1.2MB 2024-05-19

#图论 #最短路径 #数据结构 #ACM #算法

定理：对于有向加权图 G=(V,E)，若路径 P 从结点 v1 到 v_k 为最短路径，则对任意 i 和 j，都有 i 和 j 之间的最短路径也是 P 的子路径。