5.5最短路径

这个网址访问不了了，在次特别找到了缓存，方便大家查阅：http://www.cs.ecnu.edu.cn/assist/js04/ZJS045/ZJS04505/zjs045050a.htm

5.5最短路径 

在一个图中，两个结点之间可能有多条路径，且每条路径上所经过的边数可能是不同的，如果是网络，每条路径的各边权数之和也可能是不同的。我们通常把从一个指定的顶点到达另一指定顶点的各边权数之和为最小的路径称为最短路径，这               类问题亦称为最短路径问题。例如，用顶点表示城市，边表示路径，而边上的权表示里程数，于是顶点、边及里程数构成了一个有关城市的网络，我们从某一城市到达另外城市的最省路径便是一个典型的最短路径问题。               

[提高](增)

本节考虑的是带权有向图,除非特别声明,否则有向边上的权总是正的.我们称路径的开始顶点为源点,称路径的最后顶点为终点.路径的长度是该路径上各边的权之和.

 5.5.1求一个顶点到其他各顶点的最短路径

[例子]               （增）

给定带权有向图G=(V,E)，E中每条弧（w,v）都有非负的权。指定V中的一个顶点v做源点，找从源点v到图中其他各顶点的最短路径。

始点	终点	最短路径	路径长度
V1	V2	(v1,v2)	10
V1	V3	(v1,v4,v3)	50
V1	V4	(v1,v4)	30
V1	V5	(v1,v4,v3,v5)	60

1->2   10

1->5 100

1->4   30

2->3   50

3->5   10

4->3   10

5->4   60

 

12345是节点，描述节点之间的连接和权

E. W Dijkstra最短路径基本思想

以一个顶点V1作为源点，求该顶点到其他各顶点的最短路径，E.               W Dijkstra提出了一个按路径长度递增的顺序产生最短路径的方法。此方法的基本思想是：把图中所有结点分成两组，第一组包括已确定最短路径的顶点，第二组包括尚未确定最短路径的顶点               ，按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中，直到从V1出发可以到达的所有顶点都已包括在第一组中。在这过程中，总保持从V1到第一组各顶点的最短路径都不大于从V1到第二组的任何顶点的最短路径长度。另外，每个顶点对应一个距离值，第一组的顶点对应的距离值就是从V1到此顶点的最短路径长度，第二组的顶点对应的距离值是从V1到此顶点的只包括第一组的顶点为中间顶点的最短路径长度。

具体的做法

一开始第一组只包括顶点V1，第二组包括其他所有顶点。V1对应的距离值为0，第二组的顶点对应的距离值是这样确定的：若图中有弧〈V1，Vj〉，则Vj的距离为此弧的权值，否则Vj的距离为￥（或用一个很大的数表示）。然后每次从第二组的顶点中选一个其距离值为最小Vm的加入到第一组中，每往第一组中加入一个顶点Vm，就要对第二组中的各个顶点的距离值进行一次修正。若加进Vm做中间结点，使从V1到Vj的最短路径比不加Vm的路径要短，则要修改Vj的距离值。修改后再选距离值最小的顶点加入到第一组中。如此进行下去，直到图中所有顶点都包括在第一组中 ，或再也没有可加入到第一组中的顶点存在为止。

下面给出给出实现上面算法的程序

设有向图用邻接矩阵A表示，若〈V1，Vj〉是图中的弧，则A[i，j]的值等于边上所带的权值，否则A[i，j]等于一个很大的正数MAX(在下面用&表示)。开始时A[i，j]＝0表示顶点j未在第一组中，处理中用A[i，j]＝1标志第j个顶点已进入第一组。用数组ad存放邻接矩阵A，数组元素的下标等于相关联顶点序号减1。数组dist[n]的每个元素为顶点的距离值，pre[n]的每个元素为从V1到该顶点的路径上此顶点的前一个顶点的序号，若从V1到该顶点无路径，则用0作为其前一个顶点序号。算法结束时，沿着顶点Vj对应的pre[j－1]追溯，就能确定V1到Vj最短路径，其最短路径长度等于dist[j－1]。此算法起始顶点也可以不是V1，起始顶点的序号由变量k给出（即从顶点Vk出发）。源点为Vk(其中k为1)

 https://web.archive.org/web/20040118133953/http://www.cs.ecnu.edu.cn/assist/js04/Video_Audio/zm0450500.swf

完整程序

----------------------------

#include<stdio.h>

#define MAX 9999

void main()

{int ad[ ][MAX]; int k; int pre[MAX];         int dist[MAX];int n,i,j;

printf("pleas input ad[][]!");

prinf("input n");

scanf("%d",&n);

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

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

{scanf("%d",&ad[i][j]);)      

prinf("select Vk");

scanf("%d",&k)

dijkstra(ad,k,pre,dist,n);

}

 

void dijkstra (int ad[ ][], int k, int         pre[ ], int dist[ ], int n)

{

// 求有向图以顶点Vk为始点到其他各项顶点间的最短路径的dijkstra算法

int , j, p,min;

k=k－1;

for (i=0; i<n; i++) // 初始化

{

dist[i]=ad[k][i];

if (dist[i]<MAX)

pre[i]=k+1;

else

pre[i]=0;

}

pre[k]=0;

dist[k]=0; // 数组dist和pre初始化

ad[k][k]=1; // Vk加入到第一组

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

{

min=MAX;

p=－1;

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

if(ad[i][i]= =0 && dist[i]<min)         

{

p=i;

min=dist[i];

} // 在第二组中选距离值最小的顶点

if (p = = －1) break; // 以没有顶点可往第一组加

else

 

ad [p][p]=1;

// 把第二组中选出的距离最小的顶点加到第一组中

for {i=0; i<m; i++}

if (ad[i][i] = =0 && (min+ad[p][i]<dist[i])         

{

dist[i]=min+ad[p][i];

pre[i]=p+1;

}

// 更新第二组中的当前距离值和路径上前以顶点序号

}

}

-------------------

实际上，我们也可以用邻接表来存储图。下面给出采用邻接表存储结构的Dijkstra算法。

----------------------------------------------

void shortpath (head, n,         m, s)

struct headnode had[100];

int n, m, s[100];

{

int * visit, q[100], front, rear, h,         i, j, k;

struct node * p;

visit=malloc(n * sizeof (int));

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

visit[k]=0;

front=0;

rear=0;

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

s[k]=－1;

visit [m－1]=1;

s[m－1]=0;

q[rear]=m;

rear=rear+1;

while (front!=rear)

{

k=q[front];

front=front+1;

p=head[k－1].link;

while (p!=NULL)

{

j=p->vertex;

h=s[k－1]+p->weight;

if((s[j－1] = =－1)||(s[j－1]>h))

{

s[j－1]=h;

if (visit[j－1]= =0)

{

visit[j－1]=1;

q[rear]=j;

rear=rear+1

}

}

p=p->next;

}

}

}

------------------------------------------------------------

5.5.2    求每一对顶点之间的最短路径

利用Dijkstra算法实现            

要求一个有n个顶点的带权有向图的每一对顶点之间的最短路径，显而易见的解决方法是：以某一顶点为起始点，用Dijkstra算法求该点到其他顶点的最短路径，然后不断变换起始点，再用Dijkstra算法求解，即通过n次重复执行Dijkstra算法来求得每一对顶点之间的最短路径。            

但这种方法比较繁琐,下面介绍一种简便的方法               

Floyd算法            

弗洛伊德（R. W Floyd）提出了另一种算法，这种算法仍用邻接矩阵A表示带权有向图。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为A[i，j]的路径，该路径不一定是最短路径，需要进行n次试探。            

具体方法

为了方便描述试探的过程，先引入k－path的定义。定义k－path为图中任意一条从顶点u到w的、中间顶点序号不大于k的路径。比如〈u，V3，w〉至少是u到w的3－path，因为中间顶点的序号是3，当然也可认为是4－path，5－path等。若此路径存在，则u到w的0－path为〈u，w〉。               

假设已知从u到w的最短的（k－1）－path，则最短的k－path要私经过序号为k的顶点Vk，要么不经过。如果u到w的最短的k－path经过顶点Vk则它的一部分是从u到Vk的（k－1）－path，另一部分为Vk到w的（k－1）－path；否则，保持最短的u到w的（k－1）－path不变（即u到w的最短的k－path与其最短的（k－1）－path相同）。这样，经过n次试探，得到的u到w的最短的n－path为任意两点u到w的最短路径。图的邻接矩阵即表示了试探的初始状态。由w，v的任意性，可得到图中每一对顶点之间的最短路径            

下面给出求解每一对顶点之间的最短路径的程序(程序中M=9999;动画中用∝表示)

用ad数组存放图的邻接矩阵。另一个矩阵path[i，j]是从Vi到Vj的最短的k－path上Vj的前一个顶点的序号（k＝1，2，…，n），约定若Vi到Vj无路径时path[i，j]＝0。求得最短路径后由path[i，j]的值追溯，可以得到从Vi到Vj的最短路径。用p数组存放path矩阵，算法中所有数组的数组元素下标等于相关连点的序号减1，相应地k从0至（n－1）。

 

2->1  3

1->2  8

1->3  5

3->2  2

    |0     8     5|

ad=|3     0     ∝|

     |∝     2     0|

 

 

�������������这个带权有向图及其代价邻接矩阵就是我们的示范例子

Floyd算法

#include<stdio.h>

#define MAX 9999

void main()

{int ad[ ][MAX]; int k; int p[MAX]; int         n,i,j;

printf("pleas input ad[][]!");

prinf("input n");

scanf("%d",&n)

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

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

{scanf("%d",&ad[i][j]);}      

prinf("select Vk");

scanf("%d",&k)

floyd(ad,p,n);

}

void floyd(ad, p, n)

int ad[ ][M], p[ ][M], n; //ad存放邻接矩阵 p存放最短路径经过的顶点

int i, j, k;

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

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

{

if (i= =j) p[i][j]=0; // 顶点本身假设无路径

else

if (ad[i][j]<M) p[i][j]= i+1; // 置p的初始值

else p[i][j]=0;

}

for (k =0; k<n; k++) // 利用三重循环将各情况穷举

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

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

if (ad[i][k]+ad[k][j]<ad[i][j]) // 加入中间顶点k来试探

{

ad[i][j]=ad[I][k]+ad[k][j]; // 重新置两点间最短路径

p[i][j]=p[k][j]; // 将k加入p

}

}