DAG上的最短路径

如果用动态规划求DAG上的最短路径，应该先进行拓扑排序。

(1) 特殊DAG的最短路径

【问题描述】下图的拓扑排序序列为0,1,2……n-1，求结点0到其他各点的最短路径长。          邻接矩阵（未填充部分为∞）

i\j 0 1 2 3 4 5 6 7 8 9 0 3 4 5 1 5 3 2 2 3 1 5 4 3 5 1 1 6 6 7 5 8 4 9

  

【分析】

1. 状态表示：设 f(x)表示结点0到结点 x 的最短路径长度。

2. 状态转移方程：f(x)＝min(f(i)＋G[i][x])，其中结点 i 是结点 x 的前趋。边界条件：f(0)＝0

int G[N][N], n; int f[N]; f[0]=0; for (int i=1; i<n; i++) f=INF; for (int x=0; x<n; x++)  for (int i=0; i<n; i++)   f[x] = min(f[x], f+G[x]); for (int i=0; i<n; i++) cout<<f<<" ";

(2) 关键工程

参见152页“13.8 拓扑排序”。

(3) 街道

【问题描述】下图是一个 m×n 的街区。每条马路（最短的边算一条马路）上有一个数字。从左上角出发到右下角，路上只能往右或往下走。问经过的数字的和最大可以达到多少。

【分析】

转化思路：构造出一个DAG。

file:///C:/Users/123/AppData/Local/Temp/ksohtml11960/wps10.png 由于这道题道路整齐，所以求解起来更容易一些。