太原理工课程设计

为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。

那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。

迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，

V?{v1,v2,?,vn}，cost是表示G的邻接矩阵，cost[i][j]表示有向边的权。若不

存在有向边，则cost[i][j]的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含一个元素，即顶点v1。数组dist记录从源点到其他顶点当前的最短距离，其初值为dist[i]=cost[v1][i],i=1,2,??,n。从S之外的顶点集合V-S中选出一个顶点w，使dist[w]的值最小。于是从源点到达w只通过S中顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到V-S为空。

最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i]表示从源点到顶点i之间的最短路径的前驱顶点。

因此，迪杰斯特拉算法可用自然语言描述如下： 初始化S和D，置空最短路径终点集，置初始的最短路径值； S[v1]=TRUE; D[v1]=0； //S集初始时只有源点，源点到源点的距离为0； While (S集中顶点数

任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V，E），要对G中任意一对顶点有序对“v,w(v?w)”,找出v到w的最短路径。

要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。

这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。

费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点 vi到vj的最短路径。如果从vi到vj存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径和是否存在。如果存在，则比较和< vi,v1,vj>的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么可分解为和,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推，直到顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，

因此，它就是vi到vj的最短路径。

【设计功能】（用C或C++语言描述）

1．建立有向图的存储结构

2．迪杰斯特拉算法 3．费洛伊德算法

【测试实例及运行结果】

#include #include #include #define MaxVerNum 30 #define NIF 32767 #define false 0 #define true 1

typedef char VertexType; typedef int Edgetype; typedef struct{

VertexType vexs[MaxVerNum];

Edgetype edges[MaxVerNum][MaxVerNum]; int n,e; }MGraph;

void CreatGraph(MGraph *G){ int i,j,k;

printf(\多少城市和路径?\\t(example:4,5):\\t\ scanf(\ printf(\输入每个城市的信息\\n\ for(i=0;in;i++){

scanf(\ }

for(i=0;in;i++)

for(j=0;jn;j++){

if(i==j) G->edges[i][j]=0; else G->edges[i][j]=NIF; }

for(k=0;ke;k++){

printf(\输入包括这条路径的两个城市(eg:2,3):\\t\ scanf(\

printf(\ scanf(\ }

/*****************输出建立好的矩阵********************/

printf(\can easily get this matrix from your input<==\\n\\n\ for(i=0;in;i++){

printf(\ printf(\

}

printf(\ for(i=0;in;i++){

printf(\ for(j=0;jn;j++){

printf(\ if(j==G->n-1)

printf(\ } }

printf(\}

int Dijkstra(MGraph *G,int v0){ int D[MaxVerNum]; int final[MaxVerNum]; int i,v,w,min;

for(v=0;vn;++v){ final[v]=false;

D[v]=G->edges[v0][v]; } D[v0]=0;

final[v0]=true;

for(i=1;in;++i){ min=NIF;

for(w=0;wn;++w)

if(!final[w]&&D[w]

min=D[w]; }

final[v]=true;

for(w=0;wn;++w){

if(!final[w]&&(min+G->edges[v][w]edges[v][w]; } } }

printf(\is:\\n\\n\

for(i=0;in;i++){

printf(\ printf(\ }

printf(\

printf(\ for(w=0;wn;w++) printf(\

printf(\ return 1; }

int Floyd(MGraph *G,int n){

int P[MaxVerNum][MaxVerNum][MaxVerNum]; int D[MaxVerNum][MaxVerNum]; int u,v,w,i;

for(v=0;vn;++v) for(w=0;wn;++w){

D[v][w]=G->edges[v][w]; for(u=0;un;++u) P[v][w][u]=0; if(D[v][w]

P[v][w][v]=1; P[v][w][w]=1; } }

for(u=0;un;++u) for(v=0;vn;++v) for(w=0;wn;++w)

if(D[v][u]+D[u][w]n;++i)

P[v][w][i]=P[v][u][i]||P[u][w][i]; }

for(i=0;in;i++){

printf(\ printf(\ }

printf(\ for(i=0;in;i++){

printf(\ printf(\ }

printf(\ for(i=0;in;i++){

printf(\ for(v=0;vn;v++){

if(!D[i][v]||D[i][v]==NIF) printf(\ else printf(\