文档介绍：该【动态规划所有点对的最短距离 】是由【88jmni97】上传分享，文档一共【33】页，该文档可以免费在线阅读，需要了解更多关于【动态规划所有点对的最短距离 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第七章动态规划
对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E)，求所有顶点之间的最短路径和最短距离。
图的邻接矩阵表示法
1
2
3
V =
(
b
)
(
a
)
2
8
1
9
6
1
2
3
L=
0 2 9
0 6
1 ∞ 0
其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
初始时，S中仅含有源点。设u是G的某一个顶点，把从源点到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组distance记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组distance作必要的修改。一旦S包含了所有V中顶点，distance就记录了从源到所有其它顶点之间的最短路径长度。
复习Dijkstra算法
算法中，我们不断更新以下三个数组：
s数组: s[i]，当顶点i加入S时，s[i]置1
Distance数组: Distance[i]记录原点到 顶点i的最短特殊路径长度。
path数组： path[i]记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如：设源点是顶点1, path数组如下
例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。
0
1
4
1
3
0
10
50
30
60
1
1
1
1
1
s:
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)
{
Int n=();
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的距离。
——即原问题