12.1
在更新
- 第一问：
- 第二问：
12.2
(1)
- 基于Dijkstra算法改进，找从s到各点的所有路径的最小权边的最大值。
- 类似于10.38
- 给每个点定义变量capacity：从s到该点的所有路径上最小边权值的最大值
- 初始化：s的capacity为无穷,其他点的capacity为0。
- 每次选择与“最短路径树”相邻的且capcity值最大的点，加入“最小路径树”（这里即已确定capacity的点集）。第一步把s加入。
- 每次向最短路径树增加一个点u后，更新其邻居v的capacity
- v.capacity=max{v.capacity, min{u.capacity,uv.weight}}
- 返回第三行继续选点加入最小路径树。
- 最终t.capacity就是从s到t的最大吞吐量。
- 复杂度同Dijkstra,O((m+n)log n)
(2)
- 类似于课本第147页的Floyd-Warshall算法，但状态转移方程（算法44的第5行）要修改如下。
12.4
- 添加点s连向S中的点，添加t被T中的点连向。
- 对新图使用dijkstra算法
- 复杂度O(mlog n)
12.7
- 以
为源点调用dijkstra算法 - 对转置图以
为源点调用dijkstra算法 - i到j的最短路，就是i到
与 到j的最短路的和。
