如何更新最大流模型？作业题B部分正确性与O(V+E)复杂度求证

问题翻译（原问题来自图片） #

给定有向无环图（DAG）G=(V,E)，以及两个顶点s和t，设计一个线性时间算法，计算从s到t的最长路径长度。

解法正确性分析 #

网上常见的标准解法是拓扑排序+动态规划，步骤如下：

1. 对DAG做拓扑排序，得到顶点的线性序列。
2. 初始化距离数组dist[]：dist[s] = 0，其余顶点设为-∞。
3. 按拓扑序遍历每个顶点u：
   • 对u的每个邻接顶点v，更新dist[v] = max(dist[v], dist[u] + w(u,v))（无权图则为dist[u]+1，w(u,v)是边u→v的权重）。
4. dist[t]即为s到t的最长路径长度。

正确性证明 #

• 拓扑排序的特性保证：处理顶点u时，所有能到达u的路径都已处理完成，DAG无环，不会出现后续顶点反向更新u的情况，避免了循环依赖的问题。
• 动态规划的状态转移基于最优子结构：到v的最长路径，必然是通过某个前驱u的最长路径加上u→v的边权，每次更新保留当前最大距离，最终dist[t]就是所有可能路径中的最大值。
• 若dist[t]仍为-∞，说明s无法到达t，不存在有效路径。

时间复杂度O(V+E)证明 #

• 拓扑排序：用Kahn算法（入度表+队列）实现时，需遍历所有顶点统计入度，遍历所有边处理邻接关系，时间复杂度为O(V+E)。
• 动态规划遍历：每个顶点仅被处理一次；每个边仅被遍历一次（处理u时遍历其出边），这部分时间复杂度也是O(V+E)。
• 两部分操作时间相加，总复杂度为O(V+E)，满足线性时间要求。

内容的提问来源于stack exchange，提问作者DevFish