单源点最短路径算法的实现.doc

数据结构课程设计
设计说明书

单源点最短路径算法的实现

学生姓名
潘 飞
学 号
1221024012
班 级
信管1201班
成 绩

指导教师
余冬梅

数学与计算机科学学院
2014年3月7日

课程设计任务书
2013 —2014 学年第 2 学期
专业： 信息管理与信息系统 学号： 1221024030 姓名： 潘 飞
课程设计名称： 数据结构课程设计
设计题目： 单源点最短路径算法的实现
完成期限：自 2014 年 2 月 24 日至 2014 年 3 月 7 日共 2 周
设计依据、要求及主要内容（可另加附页）：
最短路径算法关键先把已知最短路径顶点集（只有一个源点）和未知的顶点分开，然后依次把未知集合的顶点按照最短路径（特别强调一下是源点到该顶点的路径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚）加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题，这对以上几个问题采用了迪杰斯特拉算法。并为本系统设置一人性化的系统提示菜单，方便使用者的使用。
本课程设计中主要完成以下内容：
1. 建立图的存储结构。
2. 解决单源最短路径问题。
3. 实现两个顶点之间的最短路径问题。
基本要求如下：
1.程序设计界面友好；
2.设计思想阐述清晰；
3.算法流程图正确；
4.软件测试方案合理、有效。

指导教师（签字）： 教研室负责人（签字）：

批准日期： 年 月 日
评语：

指导老师签名：
年 月 日
课程设计评阅

摘 要

本软件以VC++作为开发平台， 设计了关于从某个单一原点到任意顶点的一个类似于

查询，咨询系统的软件。它能够准确快速的计算出从某个单一原点到任意顶点的最短路径以

及路径长度。该类软件目前广泛运用于城市交通运输系统，为人们出行带来了方便。

关键字： VC++；最短路径； 迪杰斯特拉算法；

目录
目录 - 1 -
1、课题描述 - 1 -
2、问题分析与设计思想 - 2 -
3、概要设计 - 4 -
4、详细设计 - 6 -
4.1建立图的存储结构 - 6 -
4.2单源最短路径 - 6 -
5、程序编码 - 8 -
6、程序调试和测试 - 12 -
7、总结 - 16 -
参考文献 - 16 -

1、课题描述

在城市交通网络日益发达的今天，针对人们出行关心的各种问题，利用计算机软件建

立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边

表示各个城市之间的交通关系，所带权值为两个城市间的距离。

2、问题分析与设计思想

问题分析：
可以将该系统大致分为两个部分：
①　建立网络图的存储结构：
定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。
②　解决单源最短路径问题：
单源最短路径问题：已知有向图(带权)，期望找出从某个源点S∈V到G中其余各顶点的最短路径。

设计思想：
Dijkstra提出了一个按路径长度递增的次序产生最短路径的算法。首先，引进一个辅助
向量D，它的每个分量D[i]表示当前所找到的从源点v到每个终点vi的最短路径长度。
它的初始状态为：若v到vi有弧，则D[i]为弧上的权值，否则D[i]为无穷大。显然，
长度为:D[j] = Min{D[i] | vi 属于V} 的路径就是从v出发的长度最短的一条路径。此路
径为 (v, vi)。 那么，长度次短的路径是哪一条呢？假设该次短路径的终点是vk，则可
以证明，这条路径或者是(v, vk)，或者是(v, vj, vk)。它的长度或者是从v到vk的弧上的
权值，或者是D[j]和从vj到vk的弧上的权值之和。N
设定变量，初始化dist[]数组，使其与cost[V0][i]相对应

定义顶点V0与自身的距离为0;
定义经过的顶点个数为0；
定义顶点集合S[MAX]
初始化数组S[i]，并规定i为顶点序号
将起点V0加入数组
首先初始最短路径mindis为无穷大；
查找离顶点V0最近的顶点，并赋值距离给mindis=dist[j];
根据找到的顶点寻找下一个路径最短的顶点S[u]，并记录最短路径dis=dist[u]+cost[j]；
dis是否大于V0直接到S[u]的距离；
最短路径为dist
记录经过的顶点;
j为寻找下一个顶点的变量

添加顶点到最短路径当中；
输出顶点V0到各个顶点的最短路径
结束

图2.1 Dijkstra算法流程图
3、概要设计
存在一条从i到j的最短路径(Vi.....Vk,Vj)，Vk是Vj前面的一顶点。那么
(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最
短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的
顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离
dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路，
假设存在G=<V,E>，源顶点为V0，U={V0},dist[i]记录V0到i的最短距离，path[i]
记录从V0到i路径上的i前面的一个顶点。
1.从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；
2.更新与i直接相邻顶点的dist值。
(dist[j]=min{dist[j],dist[i]+matrix[i][j]})
3.知道U=V，停止。

流程图：

开始

初始化距离和路径

i=1

j=1;j++;j<n

i>n
i++

修改最短路径和距离

输出结果

图3.1最短路径

4、详细设计
4.1建立图的存储结构
定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具
有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。

注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的
邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储
顶点 的信息）。
邻接矩阵的存储结构：
#define MVNum 100 //最大顶点数
typedef struct
{
VertexType vexs[MVNum];//顶点数组，类型假定为char型
Adjmatrix arcs[MVNum][MVNum];//邻接矩阵，假定为int型
}MGraph;
注：由于有向图的邻接矩阵是不对称的，故程序运行时只需要输入所有有向边及其权值即可。

4.2单源最短路径
单源最短路径问题：已知有向图(带权)，期望找出从某个源点S∈V到G中其余各顶点的最
短路径。
迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。
算法思想：设有向图G=(V,E)，其中V={1,2，……n}，cost是表示G的邻接矩阵，
cost[i][j]表示有向边<i,j>的权。若不存在有向边<i,j>，则cost[i][j] 的权为无穷大（这里
取值为32767）。设S是一个集合，集合中一个元素表示一个顶点，从源点到这些顶点
的最短距离已经求出。设顶点V1为源点，集合S的初态只包含顶点V1。数组dist记
录从源点到其它各顶点当前的最短距离，其初值为dist[i]= cost[i][j]，i=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]。重复上述过程，
直到S中包含V中其余顶点的最短路径。
最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了从源
点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i]表示
从源点到顶点i之间的最短路径的前驱顶点。

5、程序编码
#include<stdio.h>
#include<stdlib.h>
#define MVNum 100
#define Maxint 32767
enum boolean{FALSE,TRUE};
typedef char VertexType;
typedef int Adjmatrix;
typedef struct{
VertexType vexs[MVNum];
Adjmatrix arcs[MVNum][MVNum];
}MGraph;
int D1[MVNum],p1[MVNum];
int D[MVNum][MVNum],p[MVNum][MVNum];
void CreateMGraph(MGraph * G,int n,int e)
{
int i,j,k,w;
for(i=1;i<=n;i++)
G->vexs[i]=(char)i;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
G->arcs[i][j]=Maxint;
printf("输入%d条边的i.j及w:\n",e);
for(k=1;k<=e;k++){
scanf("%d,%d,%d",&i,&j,&w);
G->arcs[i][j]=w;
}
printf("有向图的存储结构建立完毕！\n");
}
void Dijkstra(MGraph *G,int v1,int n)
{
int D2[MVNum],p2[MVNum];
int v,i,w,min;
enum boolean S[MVNum];
for(v=1;v<=n;v++){
S[v]=FALSE;
D2[v]=G->arcs[v1][v];
if(D2[v]<Maxint)
p2[v]=v1;
else
p2[v]=0;
}
D2[v1]=0; S[v1]=TRUE;
for(i=2;i<n;i++){
min=Maxint;
for(w=1;w<=n;w++)
if(!S[w] && D2[w]<min)
{v=w;min=D2[w];}
S[v]=TRUE;
for(w=1;w<=n;w++)
if(!S[w] && (D2[v]+G->arcs[v][w]<D2[w])){
D2[w]=D2[v]+G->arcs[v][w];
p2[w]=v;
}
}
printf("路径长度 路径\n");
for(i=1;i<=n;i++){
printf("%5d",D2[i]);
printf("%5d",i);v=p2[i];
while(v!=0){
printf("<-%d",v);
v=p2[v];
}
printf("\n");
}
}
void Floyd(MGraph *G,int n)
{
int i,j,k,v,w;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if( G->arcs[i][j]!=Maxint)
p[i][j]=j;
else
p[i][j]=0;
D[i][j]=G->arcs[i][j];
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(D[i][k]+D[k][j]<D[i][j]) {
D[i][j]=D[i][k]+D[k][j];
p[i][j]=p[i][k];
}
}
}
}
void main()
{
MGraph *G;
int m,n,e,v,w,k;
int xz=1;
G=(MGraph *)malloc(sizeof(MGraph));
printf("输入图中顶点个数和边数n,e:");
scanf("%d,%d",&n,&e);
CreateMGraph(G,n,e);
while(xz!=0){
printf("************求城市之间最短路径************\n");
printf("=========================================\n");
printf("1.求一个城市到所有城市的最短路径\n");
printf("2.求任意的两个城市之间的最短路径\n");
printf("=========================================\n");
printf("请选择 :1或2，选择0退出:\n");
scanf("%d",&xz);
if (xz==2){
Floyd(G,n);
printf("输入源点（或起点）和终点:v,w:");
scanf("%d,%d",&v,&w);
k=p[v][w];
if (k==0)
printf("顶点%d 到 %d 无路径!\n",v,w);
else
{
printf("从顶点%d 到 %d 最短路径路径是:%d",v,w,v);
while (k!=w){
printf("--%d",k);
k=p[k][w];
}
printf("--%d",w);
printf("径路长度:%d\n",D[v][w]);
}
}
else
if(xz==1)
printf("求单源路径，输入源点v :");
scanf("%d",&v);
Dijkstra(G,v,n);

}
printf("结束求最短路径，再见!\n");
}

6、程序调试和测试

测试实例1：利用如下图所示的有向图来测试。

3

1

13
7

17

61

32 74
76

6

4
2
64

26
56
5
45

图5.1有向图测试

实例1运行结果：

图5.2有向图测试运行结果

测试实例2：利用下图求无向图的最短路径。

7
4
6
3
5
2
1
2553 704 695 812 511 349 615 2638 1579 1385
5.3无向图测试

图5.4无向图测试结果

7、总结
该课程设计主要是从日常生活中经常遇到的交通网络问题入手，进而利用计算机去建
立一个类似交通咨询系统，以处理和解决人们关心的各种问题（当然此次试验最终主
要解决的问题是：最短路径问题）。
这次试验中我深刻的了解到了树在计算机中的应用是如何的神奇与灵活，对于很多的
问题我们可以通过树的相关知识来解决，特别是在解决最短路径问题中，显得尤为重
要。经过着次实验，我了解到了关于树的有关算法，如：图的存储结构，迪杰斯特拉算法等，
对树的学习有了一个更深的了解。

参考文献
【1】《数据结构》严蔚敏.清华大学出版社.
【2】《数据结构课程设计》苏仕华.极械工业出版社.

- 15 -