数据结构课程设计报告--Dijkstra算法求最短路径(2)

(1) 输入顶点个数n，边的条数，初始化邻接矩阵。 (2)初始化所每条边的权值与D[h]中

(3) ① 找出v0到图中其他各点的最小值

② 经过改最小值的点到除它外其他各点的最小值 ③ 直到s中的所有值全部被处理过， (4) 输出各最短路径的长度D[w]

算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。

第三章 详细设计和编码

3.1框架的建立

typedef char VertexType;//定义图的顶点为字符型

typedef int VRType; //顶点关系类型 typedef int InfoType;//该弧相关信息

typedef struct ArcCell{ VRType adj;//权值

InfoType *info;//弧相关信息的指针 }ArcCell;

typedef struct{

VertexType vexs[MAX_VERTEX_NUM];//一维数组，存储顶点 ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 ：二维数组，存储边和弧

int vexnum,arcnum;//图的当前顶点数和弧数 }MGrph; //邻接矩阵表示的图

3.1.1顶点的定义typedef char VertexType;//定义图的顶点为字符型 顶点的最大个数25

3.1.2ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];二维数组用于存放邻接矩阵，每个位置代表的值为图中的权值，其余用无穷大3000表示。

3.2点结构体的定义

/* 确定位置函数 */ int LocateVex(MGrph *G,VertexType v) {

int j,b;

6

for(b=0;bvexnum;b++)//在所有顶点中寻找 if(G->vexs[b]==v)//找到所找的顶点在b位置 { j=b; break; }//if return(j); } //LocateVex

3.3创立带权值有向图

首先输入该有向图的顶点数n,然后依次输入各个顶点及边长（输入的顶点的序号应该小于顶点的数目）。

/* 有向图的建立 */ void Creat_YG(MGrph *G) { int i,k,j,n;

VertexType v1,v2; int w=1; printf(\请输入顶点个数和弧数 如括号里的方式（3,3）:\读入顶点个数和弧的个数 scanf(\读出边和弧的信息 printf(\换行输出 for(i=0;ivexnum;i++) { printf(\请输入图的第%d个顶点:\输入指定的顶点 w++; fflush(stdin); scanf(\ printf(\ }

for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) { G->arcs[i][j].adj=INFINITY; G->arcs[i][j].info=NULL; }

for(k=0;karcnum;k++) {//输入各弧并构造邻接矩阵 printf(\请输入边的起点和终点和权值如（v1,v2,n）:\起始点和终点和两点之间对应的权值

fflush(stdin); scanf(\ printf(\ i=LocateVex(G,v1);//确定v1的位置 j=LocateVex(G,v2);//确定v2的位置

7

G->arcs[i][j].adj=n;//边的权值赋为1，如需要权值操作则相应修改一下即可 G->arcs[i][j].info=NULL;//如需要有相关信息则相对应输入，在这里我设置为空 }//第二个for getchar(); } //Creat_YG

void juzhen(MGrph *G){//用矩阵来存储并显示出结果 int i,j,k;

printf(\邻接矩阵显示：\\n\ printf(\

for(i=0;ivexnum;i++) printf(\ for(j=0;jvexnum;j++) {

printf(\ printf(\ for(k=0;kvexnum;k++) {

if(G->arcs[j][k].adj

else printf(\ 3000\无权值的直接输出最大值

}

}

3.4邻接矩阵的显示

在图的邻接矩阵显示中，分别利用for循环输出了矩阵的行列标，使矩阵很明了。

void juzhen(MGrph *G){//用矩阵来存储并显示出结果 int i,j,k;

printf(\邻接矩阵显示：\\n\ printf(\

for(i=0;ivexnum;i++) printf(\ for(j=0;jvexnum;j++) {

printf(\ printf(\ for(k=0;kvexnum;k++) {

8

if(G->arcs[j][k].adj

else printf(\ 3000\无权值的直接输出最大值

} } }

3.5递归函数应用

3.5.1思想是patn[]数组来表示前驱顶点的位置，然后递归输出每个顶点的前驱

void Short(MGrph *G,int path[],int i,int w){

//递归函数是用来输出从源点出发到终点之前的顶点 //思想是patn[]数组来表示前驱顶点的位置，然后递归输出每个顶点的前驱 int k; k=path[i];

if(k!=w) Short(G,path,k,w );

printf(\输出k位置的顶点值 }

3.6 Dijkstra 算法实现最短路径

设图以邻接矩阵cost存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权值用无穷大表示。从顶点V0到其它各顶点间的最短路径的具体步骤如下：

a) 变量定义：

定义整型数组S[],这是一个顶点集合，初始时该集合只有源点v0，然后逐步将以求得最短路径的顶点加入到该集合中，直到全部顶点都在集合S中，算法结束。定义两个整型变量dis、mindis均用来标志图中最短的那一条路径。 b) 初始化：

初始化dist数组的值即为cost数组中存放的权值。 dist[i]=cost[v0][i]

初始化求到每个顶点的最短路径时都经过v0顶点。path[i].pnode[0]=v0

初始化记录经过的顶点数都为0。 path[i].num=0; 初始化顶点集合s为空，即还未开始。 s[i]=0; c) 源点的选择:

将v0顶点加入到顶点集合s中。 s[v0]=1

d) 利用for循环选择一个终点Vj,使其满足V0到Vj距离最短，同时将Vj

加入集合S中。

e) 根据j顶点调整当前的最短路径，若满足dist[i]> dist[j]+cost[j][i],

则修改dist[i]的值。同时V0到Vi的最短路径中经过的顶点数加1，即path[i].num++; 并将经过的顶点存入数组pnode即path[i].pnode[path[i].num]=j

f) 此时一趟求最短路径完毕，将终点V1添加到路径中。

9

g) 循环执行d),e),f)操作，直到全部顶点加入到S中。

第四章 上机调试

4.1记录调试过程中错误和问题的处理

1) 当输入格式不符合程序要求时，会出现循环

2) 当两顶点间没有路径时，权值为无穷大，但在本程序中只能用一个具体的数字2000代替抽象的无穷大。

3) 在程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况，并对程序规格说明作调整和改动。 4.2算法的时间和空间性能分析 4.2.1时间复杂度

对于n个顶点的有向图，求一个顶点到其他顶点的最短路径的时间为O(n)，调整最短路径的循环共执行n-1次，是二层循环，所以，时间复杂度是O（n2）。 4.2.2空间复杂度

采用邻接矩阵存储有向图，应处理每两个顶点之间的关系，所以空间复杂度为O（n2）。 4.3算法设计、调试的经验和体会

Dijkstra算法在上课的时候曾作为重点讲过，所以在做查找最短路径的算法时很流畅，但是在输出最短路径的时候遇到了很大的阻力。因为在定义结点时，使用的是结构体数组，所以当处理V0到每个结点的最短路径时，导致无法具体记录经过的顶点数，只能记录源点、终点前一顶点以及终点。所以本程序在输出最短路径时有较大的瑕疵，还需进一步修改。

10