lecture-11-4动态规划所有点对的最短距离

第七章动态规划7.5所有点对的最短路径问题对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E)，求所有顶点之间的最短路径和最短距离。图的邻接矩阵表示法123V=(b)(a)28196123L=

029061∞0复习Dijkstra算法其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时，S中仅含有源点。设u是G的某一个顶点，把从源点到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组distance记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组distance作必要的修改。一旦S包含了所有V中顶点，distance就记录了从源到所有其它顶点之间的最短路径长度。算法中，我们不断更新以下三个数组：s数组:s[i]，当顶点i加入S时，s[i]置1Distance数组:Distance[i]记录原点到顶点i的最短特殊路径长度。path数组：path[i]记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如：设源点是顶点1,path数组如下

例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。0141301050306011111s:distance:path:由源点1到顶点5的路径为：1->4->3->5方法一：重复调用Dijkstra算法n次可轮流以每一个顶点为源点，重复调用狄克斯特拉算法函数Dijkstra()n次，即可求得所有顶点之间的最短路径和最短距离。利用Dijkstra()函数求所有顶点之间的最短路径算法如下。其中，distance[i][j]中存放着从顶点i到顶点j的最短距离，path[i][j]中存放着从顶点i到顶点j的最短路径的前一顶点下标。voidShortPath(AdjMWGraph&G,int**distance,int**path){Intn=G.NumOfVertices();for(inti=0;i<n;i++)Dijkstra(G,i,distance［i］,path［i］);}由于狄克斯特拉算法的时间复杂度是O(n2)，所以n次调用狄克斯特拉算法的时间复杂度是O(n3)。该问题具有最优子结构性质例如上图中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。子问题的构造原问题：每个顶点到其他所有顶点的最短距离最小的子问题D0：从顶点i（不得经过任何其他顶点）到顶点j的距离；子问题D1：从顶点i（可以经过顶点1，不得经过其他任何其他顶点）到顶点j的距离。子问题Dk：从顶点i（可以经过顶点1、顶点2、……顶点k，不得经过任何其他顶点）到顶点j的距离。子问题Dn：从顶点i（可以经过顶点1、顶点2、……顶点n）到顶点j的距离。

——即原问题递推关系的建立由di,jk-1推出di,jk的过程如下若k=0,

di,jk=L[i][j](因为从i到j不允许经过任何其他顶点）若1≤k≤n,

di,jk=min{di,jk-1,di,kk-1+dk,jk-1}子问题Dk-1：从顶点i（可以经过顶点1、顶点2、……、顶点k-1）到顶点j的距离。

子问题Dk：从顶点i（可以经过顶点1、顶点2、……顶点k-1、顶点k）到顶点j的距离。从子问题Dk-1：到子问题Dk，仅仅多考虑了一个顶点k。我们需要重新考虑从i到j的距离：

顶点i到顶点j，是不是从k走会更近？如果从顶点i到顶点j从顶点k走更近，则i到j的距离di,jk=i到k的距离di,kk-1

+

k到j的距离dk,jk-1如果顶点i到顶点j从顶点k走更远，甚至走不通，则保持原来的距离不变di,jk

=di,jk-1

。由di,jk-1推出di,jk的过程，主要考虑的是顶点k的加入会引起什么变化？由不允许路过顶点k到允许路过顶点k，有些点间的距离是否会变的更近。例：考虑下图所示的带权有向图，求所有顶点之间的最短距离。V=(b)(a)12328196123L=

029061∞0计算过程12328196029061∞0D0=029806130D1=028806130D2=028706130D3=Di,jk：从顶点i（可以经过顶点1、顶点2、……顶点k）到顶点j的距离。在D1中，第1行和第一列是不变的，因为说从顶点1到顶点j或顶点j到顶点1：允许经过顶点1是没有意义的D1[2][3]:从顶点2到顶点3的距离（可以经过顶点1）（1）不经过顶点1：仍是D0[2][3]=6；（2）过顶点1：D0[2][1]+D0[1][3]=8+9=17

取最小值6D1[3][2]:从顶点3到顶点2的距离（可以经过顶点1）（1）不经过顶点1：仍是D0[3][2]=∞

；（2）过顶点1：D0[3][1]+D0[1][2]=1+2=3

取最小值3D2[1][3]:从顶点1到顶点3的距离（也可以经过顶点2）（1）不经过顶点2：仍是D1[1][3]=9；（2）过顶点2：D1[1][2]+D1[2][3]=2+6=8

取最小值8算法设计重要发现：在从Dk-1到Dk的计算过程中中，第k行和第k列是不变的。（因为说从顶点k到顶点j或顶点j到顶点k允许经过顶点k是没有意义的）

而在从Dk-1到Dk的计算过程中也只用到第k行和第k列，也就是说，在这一步的计算过程中用到的数据都不会被覆盖。故在算法中仅使用一个矩阵D即可FLOYD算法FLOYD(int*L,intn){int*D=(int*)malloc((n+1)*(n+1)*sizeof(int));DL{将数组L复制到D};for(k=0;k<n;k++)

for(i=0;i<n;i++)

for(j=0;j<n;j++)

D[i*n+j]=min(D[i*n+j],D[i*n+k]+D[k*n+j]);}7.60-1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?目标：使装入背包中物品的总价值最大约束条件：装入的物品总重不得超过C海盗盗宝问题海盗有一背包，最大容积为9，现有5件宝物：体积si分别是2、3、4、5和4公斤价值vi分别是3、7、5、9和8

请给出装载方案，使背包价值达到最大。S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8C=9一开始，见物品就装，物品1、2、3全装入，背包装满了，得到背包总价值为15，这是不是最大价值呢？S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8考虑只有前三个物品的情况物品4该不该装？有两个选择：（1）不装，背包价值不变，为15S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9（2）装入，它占去的体积为5，得到价值为9，剩下容积4最多可以装下多大价值？考虑只有前4个物品的情况这是一个n=3(从前三个物品中选择），容量c=4的子问题。目前最优：装入物品2和物品4，总价值为16若已知这个子问题的解是：装物品2，得价值为7。S1=2v1=3S3=4v3=5S4=5v4=9（2）装入物品4，它占去的体积为5，得到价值为9，剩下容积4最多可以装下多大价值？S2=3v2=7S1=2v1=3S3=4v3=5S4=5v4=9S5=4v5=8考虑5个物品的情况S2=3v2=7物品5该不该装？(1)不装，得到背包价值仍为16（2）若装入物品5，占用体积为4，得价值为8，背包剩余容积为5。如何在前4个物品中选择装入，使背包价值最大化？这是n=4,c=5的一个子问题。若得到该子问题的解为：装入物品1、2，得价值为10S1=2v1=3S3=4v3=5S5=4v5=8考虑5个物品的情况S2=3v2=7目前最优：装入物品5和1、2，总价值为18>16S4=5v4=9子问题的构造当n=1时:只有一个物品，s1=2,v1=3

若背包容量c=0、1，则无法装入物品1，得到背包价值为0若背包容量c=2、3、4、5、6，7，8，9则可装入物品1，得到背包价值为3。C[1][0]=0C[1][1]=0C[1][2]=3C[1][3]=3C[1][4]=3C[1][5]=3C[1][6]=3C[1][7]=3C[1][8]=3C[1][9]=3考虑两个物品的情况当n=2时，有两个物品，s1=2,v1=3，s2=3,v2=7

若背包容量c=0、1，得到背包价值为0若背包容量c=2，可装入物品1，得总价值m[2][2]=3若背包容量c=3，m[2][3]=7若背包容量c=4,m[2][4]=7若背包容量c=5,m[2][5]=10若不装物品2，m[2][3]=m[1][3]=3若装入物品2，m[2][3]=v[2]+m[1][3-3]=7+0=7m[2][6]=10m[2][7]=10m[2][8]=10m[2][9]=10若不装物品2，m[2][5]=m[1][5]=3若装入物品2，m[2][5]=v[2]+m[1][5-3]=7+3=7递推关系的建立用m[i][j]来表示从前i个物品中选取物品装入容量为j的背包所得的最大价值。则要寻求的是m[n][c]。m[i][j]是以下两个值的最大值

（1）m[i-1][j]:即不装入物品i,背包价值与仅考虑前i-1个物品时情况相同；（2）v[i]+m[i-1][j-s[i]]:即装入物品i,再从前i-1个物品中选取，使背包剩余容积j-s[i]价值最大化。构造价值数组S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8012345678900000000000100333333332003771010101010300377101012121240037710101216165018背包容量j从前i个物品中选取S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8012345678900000000000100333333332003771010101010300377101012121540037710101216165018背包容量j从前i个物品中选取构造最优解012345678900000000000100333333332003771010101010300377101012121540037710101216165003781011151618因m[5][9]>m[4][9],物品5被装入，剩余c=9-s5=5因m[4][5]>m[3][5],物品4被装入，剩余c=9-s4=0voidKnapsack(inttv[],int

w[],int

c,int

n,float

m[][N]){//构造价值数组m

inti,j;for(i=0;i<=n;i++)m[i][0]=0;for(j=0;j<=c;j++)m[0][j]=0;for(i=1;<n;i++)//计算前n-1行

{for(j=1;j<w[i];j++)m[i][j]=m[i-1][j];

for(j=w[i];j<=c;j++){t=v[i]+m[i-1][j-w[i]];if(t>m[i-1][j])

m[i][j]=t;elsem[i][j]=m[i-1][j];}}

//计算最后一行的m[n][c]t=v[n]+m[n-1][c-w[n]];If(t>m[n-1][c])

m[n][c]=telsem[n][c]=m[n-1][c];}voidTrackback(int

m[][N],intw[],intc,intn,intx[]){int

i,j;for(i=n;i>0;i--)

if(m[i][c]==m[i-1][c])x[i]=0else