(15)--第5章 图-单源最短路径.ppt

第5章图;什么是最短路径;典型用途：交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使总费用（或总时间）最少？

问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。;一顶点到其余各顶点;在这条路径上，必定只含一条弧，并且这条弧的权值最小。;其余最短路径的特点：;1.初始化：先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。

2.选择：从这些路径中找出一条长度最短的路径（v0,u）。

3.更新：然后对其余各条路径进行适当调整：

若在图中存在弧（u,vk），且（v0,u）+（u,vk）（v0,vk）,

则以路径（v0,u,vk）代替（v0,vk）。

在调整后的各条路径中，再找长度最短的路径，依此类推。;主：邻接矩阵G[n][n](或者邻接表)

辅：

数组S[n]：记录相应顶点是否已被确定最短距离

数组D[n]：记录源点到相应顶点路径长度

数组Path[n]：记录相应顶点的前驱顶点

;①初始化：

● 将源点v0加到S中，即S[v0]?=?true；

● 将v0到各个终点的最短路径长度初始化为权值，即D[i]?=?G.arcs[v0][vi]，(vi∈V???S)；

● 如果v0和顶点vi之间有弧，则将vi的前驱置为v0，即Path[i]?=?v0，否则Path[i]?=??1。

②选择下一条最短路径的终点vk，使得：

D[k]?=?Min{D[i]|vi∈V???S};③将vk加到S中，即S[vk]?=?true。

④更新从v0出发到集合V???S上任一顶点的最短路径的长度，同时更改vi的前驱为vk。

若S[i]=false且D[k]+G.arcs[k][i]D[i]，则D[i]=D[k]+G.arcs[k][i];Path[i]=k;。

⑤重复②～④?n???1次，即可按照路径长度的递增顺序，逐个求得从v0到图上其余各顶点的最短路径。;2019年5月13日;2019年5月13日;voidShortestPath_DIJ(AMGraphG,intv0){

//用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径

n=G.vexnum; //n为G中顶点的个数

for(v=0;vn;++v){ //n个顶点依次初始化

S[v]=false; //S初始为空集

D[v]=G.arcs[v0][v]; //将v0到各个终点的最短路径长度初始???

if(D[v]MaxInt)Path[v]=v0;//v0和v之间有弧，将v的前驱置为v0

elsePath[v]=-1; //如果v0和v之间无弧，则将v的前驱置为-1

}//for

S[v0]=true; //将v0加入S

D[v0]=0; //源点到源点的距离为0 ;时间复杂度：O(n2)