第8章图-4（最短路径）

考虑带权有向图，把一条路径（仅仅考虑简单路径）上所经边的权值之和定义为该路径的路径长度或称带权路径长度。8.5.1路径的概念从源点到终点可能有多条路径，把路径长度最短的路径称为最短路径。vv1v2uc1c2c3

cm路径长度=c1+c2+…+cm路径：（v，v1，v2，…

，u）8.5最短路径1/43带权有向图012315123顶点0到3：最短路径：0→1→3最短路径长度：2很多情况下，两个顶点的最短路径不一定唯一;但最短路径长度一定是唯一的。2/438.5.1路径的概念如何求图中的最短路径？Dijkstra算法（单源最短路径）Floyd算法（多源最短路径）3/438.5.1路径的概念

问题描述(单源最短路径问题)：给定一个带权有向图G与源点v，求从v到G中其他顶点的最短路径，并限定各边上的权值不小于0。8.5.2Dijkstra算法求解算法之一：Dijkstra算法4/438.5.2Dijkstra算法设G=(V，E)是一个带权有向图，把图中顶点集合V分成两组：SvU=V-Su第1组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径v，…

，u，就将u加入到集合S中，直到全部顶点都加入到S中，算法就结束了）。第2组为其余未求出最短路径的顶点集合（用U表示）。每一步求出v到U中一个顶点u的最短路径，并将u移动到S中。直到U为空。Dijkstra求解思路5/438.5.2Dijkstra算法

（1）初始化：S只包含源点即S={v}，v的最短路径为0。U包含除v外的其他顶点，U中顶点i距离为边上的权值（若v与i有边<v，i>）或∞（若i不是v的出边邻接点）。Dijkstra算法的过程SvU=V-Siv与U中顶点i的边6/438.5.2Dijkstra算法（2）从U中选取一个距离v最小的顶点u，把u加入S中（该选定的距离就是v

u的最短路径长度）。SvU=V-Suv与U中顶点u的边最小7/438.5.2Dijkstra算法

（3）以u为新考虑的中间点，修改U中各顶点j的最短路径长度：若从源点v

j（j∈U）的最短路径长度（经过顶点u）比原来最短路径长度（不经过顶点u）短，则修改顶点j的最短路径长度。SvU=V-Suj两条路径进行比较：若经过u的最短路径长度更短，则修正8/438.5.2Dijkstra算法顶点v

j的最短路径长度＝MIN(cvk+wkj，cvj)SvU=V-Sujuvj...cvu……cvj边wujv

j的路径：不经过顶点u经过顶点u修改方式9/438.5.2Dijkstra算法（4）重复步骤（2）和（3）直到所有顶点都包含在S中。vj考虑中间其他所有顶点k，通过比较得到v

j的最短路径k10/438.5.2Dijkstra算法如何存放最短路径长度：用一维数组dist[j]存储！源点v默认，dist[j]表示源点

顶点j的最短路径长度。如dist[2]=12表示源点

顶点2的最短路径长度为12。算法设计（解决2个问题）11/43如何存放最短路径：从源点到其他顶点的最短路径有n-1条，一条最短路径用一个一维数组表示，如从顶点0

5的最短路径为0、2、3、5，表示为path[5]={0,2,3,5}。所有n-1条最短路径可以用二维数组path[][]存储。12/438.5.2Dijkstra算法改进的方法是采用一维数组path来保存：若从源点v

j的最短路径如下：则一定是从源点v

u的最短路径？vuj…a…vuj…a…b反证法证明：而通过b的路径更短，则v→…

a→…

u→j不是最短路径是v

u的最短路径与假设矛盾，问题得到证明。v

j最短路径中j的前一个顶点13/438.5.2Dijkstra算法从path[j]推出的逆路径：j，w，u，v对应的最短路径为：v→u→w→jvwjpath[j]=wuv

j的最短路径:path[w]=upath[u]=v14/438.5.2Dijkstra算法0132456476168566241S U

dist[]path[]012345

6012345

6{0}{1,2,3,4,5,6}{0,4,6,6,∞,∞,∞}{0,0,0,0,-1,-1,-1}{0,1}{2,3,4,5,6}{0,4,

5,6,11,∞,∞}{0,0,1,0,1,-1,-1}{0,1,2}{3,4,5,6}{0,4,

5,

6,11,

9,∞}{0,0,1,0,1,2,-1}Dijkstra算法示例演示最小的顶点：1最小的顶点：215/438.5.2Dijkstra算法0132456476168566241S

U

dist[]path[]012345601234

5

6{0,1,2}{3,4,5,6}{0,4,

5,6,11,

9,∞}{0,0,1,0,1,2,-1}最小的顶点：3{0,1,2,3}{4,5,6}{0,4,

5,6,11,9,

∞}{0,0,1,0,1,2,-1}最小的顶点：5{0,1,2,3,5}{4,6}{0,4,

5,6,10,9,

17}{0,0,1,0,5,2,5}16/438.5.2Dijkstra算法0132456476168566241S U

dist[]path[]01234

5

6012345

6最小的顶点：4{0,1,2,3,5}{4,6}{0,4,

5,6,10,9,

17}{0,0,1,0,5,2,5}{0,1,2,3,5,4}{6}{0,4,

5,6,10,9,

16}{0,0,1,0,5,2,4}最小的顶点：6{0,1,2,3,5,4,6}{}{0,4,

5,6,10,9,

16}{0,0,1,0,5,2,4}最终结果17/438.5.2Dijkstra算法Dijkstra算法如下（v为源点编号）：voidDijkstra(MatGraphg，intv){intdist[MAXV]，path[MAXV];

ints[MAXV];

intmindis,i,j,u;

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

{dist[i]=g.edges[v][i];

//距离初始化

s[i]=0;

//s[]置空

if(g.edges[v][i]<INF)//路径初始化

path[i]=v; //顶点v到i有边时 else

path[i]=-1; //顶点v到i没边时

}

s[v]=1; //源点v放入S中dist和path数组初始化18/438.5.2Dijkstra算法 for(i=0;i<g.n;i++)

//循环n-1次

{ mindis=INF;

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

{ if(s[j]==0&&dist[j]<mindis)

{ u=j;

mindis=dist[j];

} } }

if(dist[u]<INF)s[u]=1;

//顶点u加入S中

elsebreak;当dist[u]=∞时，说明源点v到u没有路径可以推出源点v到U（V-S）中所有顶点均没有路径？19/438.5.2Dijkstra算法 for(j=0;j<g.n;j++)

//修改不在s中的顶点的距离{ if(s[j]==0)

{ if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j]){ dist[j]=dist[u]+g.edges[u][j];

path[j]=u;

} }

}

Dispath(dist,path,s,g.n,v); //输出最短路径}Dijkstra算法的时间复杂度为O(n2)。调整20/438.5.2Dijkstra算法

求06的最短路径长度：013245646168566241path[6]=4path[4]=5path[5]=2path[2]=1path[1]=0到源点最短路径为：0→1→2→5→4

求06的最短路径：dist={0,4,

5,6,10,9,

16}0

1

2

3

4

5

6从顶点0

6的最短路径长度为16path={0,0,1,0,5,2,4}0

1

2

3

4

5

6利用dist和path求最短路径长度和最短路径21/438.5.2Dijkstra算法S={0,1,2,3,5,4,6}dist={0,4,

5,6,10,9,

16}源点v=0观察求解结果递增45691016源点到各个顶点的最短路径长度

按顶点进入S的先后顺序，最短路径长度越来越长。

一个顶点一旦进入S后，其最短路径长度不再改变（调整）。结论：0

1

234

5622/438.5.2Dijkstra算法Dijkstra算法不适合负权值的情况01212-3v=0，S={0},v到1的距离为1，v到2的距离为2选取顶点1，S={0,1},v到1的距离为1：以后不再调整实际上v到1的最小距离为2-3=-1用一个反例说明23/438.5.2Dijkstra算法影响世界的十大算法1.归并排序，快速排序和堆排序2.傅立叶变换与快速傅立叶变换3.Dijkstra算法4.RSA算法（一种加密算法）5.安全哈希算法6.整数因式分解7.链接分析（Google的PageRank算法）8.比例积分微分算法9.数据压缩算法（以哈夫曼算法为基础）10.随机数生成算法24/438.5.2Dijkstra算法

问题描述(多源最短路径)：对于一个各边权值均大于零的有向图，对每一对顶点i≠j，求出顶点i与顶点j之间的最短路径和最短路径长度。1936~2001求解算法：Floyd算法8.5.3Floyd算法25/438.5.3Floyd算法

假设有向图G=(V，E)采用邻接矩阵存储。设置一个二维数组A用于存放当前顶点之间的最短路径长度，分量A[i][j]表示当前顶点i

j的最短路径长度。算法：迭代（递推）思路Ak[i][j]：i

j的路径上所经过的顶点编号不大于k的最短路径长度。ij0～k的顶点按顶点0，1，2，…的顺序依次考虑递推产生一个矩阵序列：A0

A1

…

Ak

…

An-1。26/438.5.3Floyd算法

初始时，有A-1[i][j]=g.edges[i][j]。若Ak-1已经求出。

考虑顶点k：求从i

j的最短路径经过编号为k顶点的情况。递推产生一个矩阵序列：A0

A1

…

Ak

…

An-1。27/438.5.3Floyd算法Ak[i,j]=MIN{Ak-1[i,j]，Ak-1[i,k]+Ak-1[k,j]}ki…Ak-1[i,k]…Ak-1[k,j]j……Ak-1[i,j]A-1[i][j]=g.edges[i][j]Ak[i,j]=MIN{Ak-1[i,j]，Ak-1[i,k]+Ak-1[k,j]}0≤k≤n-1ki

j有两条路径，取最短的一条！28/438.5.3Floyd算法（1）用二维数组A存储最短路径长度：Ak[i][j]表示考虑顶点0~k后得出的i

j的最短路径长度。An-1[i][j]表示最终的i

j的最短路径长度。算法设计（解决2个问题）（2）用二维数组path存放最短路径：pathk[i][j]表示考虑顶点0~k后得出的i

j的最短路径。pathn-1[i][j]表示最终i

j的最短路径。29/438.5.3Floyd算法pathx[i][j]表示考虑过0～x的顶点得到i

j的最短路径，存放该路径上顶点j的前一个顶点编号。ij……bpathk-1[i][j]=bk……apathk-1[k][j]=a如何用path存放最短路径？考虑过0～k-1顶点的情况30/438.5.3Floyd算法若经过顶点k的路径更短：

pathk[i][j]=a=pathk-1[k][j]否则：

pathk[i][j]=b=pathk-1[i][j]不改变现在考虑顶点kij……bpathk-1[i][j]=bk……apathk-1[k][j]=a31/438.5.3Floyd算法Floyd算法示例演示057∞∞024∞∞013320501233273124A-10123005∞71∞042233023∞∞10path-101230-10-101-1-111222-123-1-13-1∞和i

i：-1(i,j)有边：i求path32/438.5.3Floyd算法501233273124A00123005∞71∞042233023∞∞10path001230-10-101-1-111222-123-1-13-1考虑顶点0：没有任何路径修改A0=A-1，path0=path-133/438.5.3Floyd算法012353273124A10123005∞71∞042233023∞∞10path101230-10-101-1-111222-123-1-13-1考虑顶点1：0→2：由无路径改为0→1→2，长度为9，path[0][2]改为19134/438.5.3Floyd算法012353273124A20123005971∞042233023∞∞10path201230-10101-1-111222-123-1-13-1考虑顶点2：721→0：由无路径改为1→2→0，长度为7，path[1][0]改为23→1：由无路径改为3→2→1，长度为4，path[3][1]改为23→0：由无路径改为3→2→0，长度为4，path[3][0]改为2424235/438.5.3Floyd算法012353273124A3012300597170422330234410path301230-101012-111222-123223-1考虑顶点3：0→2：由0→1→2改为0→3→2，长度为8，path[0][2]改为31→2：由1→2改为1→3→2，长度为3，path[1][2]改为31→0：由1→2→0改为1→3→2→0，长度为6，path[1][0]改为283623336/438.5.3Floyd算法012300587160322330234410由A3数组可以直接得到两个顶点之间的最短路径长度。如A3[1][0]=6说明顶点1到0的最短路径长度为6。

求最短路径长度：A3path301230-103012-131222-123223-16最终结果37/438.5.3Floyd算法01230-103012-131222-123223-1求顶点1

0的最短路径：path3[1][0]=2path3[1][2]=3path3[1][3]=1查找的顶点序列为0、2、3、1，则顶点1

0的最短路径为1→3→2→0。

求最短路径：A3012300587160322330234410path332138/438.5.3Floyd算法Floyd算法如下：voidFloyd(MatGraphg) //求每对顶点之间的最短路径{intA[MAXVEX][MAXVEX]; //