dijkstra算法的实现.doc

文档介绍：合肥学院
题目:Dijkstra算法的实现
问题分析和任务定义
:对任意图,选择合适的数据结构表示图,在此基础上实现求解最短路径的Dijkstra算法。
要求:对所设计的图的数据结构,提供必要的基本功能。
:建立图的表示模块,顶点的插入和删除操作模块;在建立图之后从单源点开始求最短路径,并显示出来!
2、实现功能:

,显示出来从顶点到各个顶点的最短路径
3、测试用例:
:a)顶点:3;边值信息:0 1 2;1 0 3;1 2 5;2 1 6;0 0 0;
b)顶点:0;边值信息:0 0 0;
:a)顶点:#;
b)顶点:3;边值信息:0 1 #;
:图1
V0
V1
V2
2
3
1
2
5
4
图1. 有向图
问题分析: 题目要求选择合适的数据结构表示图,本程序邻接矩阵存储结点和弧等图的有关信息
对用邻接矩阵表示的有向图,从某一顶点出发(称为源点)到该图其他各顶点(称为终点)有无路径?最短路径是什么?路径长为多少?问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。对邻接矩阵arsc[n][n]中的每一个元素只能有三种情况:
①当i=j 时,p[i][j]=0;
②当顶点i到j无边时,p[i][j]= MAX;
③当顶点i到j 有边且权值为arcs[i][j]时,p[i][j]= arcs[i][j].
由于题目中没有规定输出格式,本程序以顶点序号的形式将最短路径输出到终端上去,并输出该最短路径的长度。
二、数据结构的选择和概要设计
1) 数据存储结构
以邻接矩阵存储有向图,如图2中有向图G所示,其邻接矩阵为图 3 arcs。
1
5
3
6
4
2
45
10
50
20
15
30
3
15
10
20
0
50
10
∞
45
∞
0
15
50
10
∞
20
0
∞
∞
∞
∞
15
∞
20
∞
0
35
∞
∞
∞
∞
30
0
∞
0
∞
3
∞
∞
∞
35
图2.
有向图的邻接矩阵arcs[i][j]定义为
int arcs[n][n];
2)概要设计
对用邻接矩阵表示的有向图,从某一顶点出发(称为源点)到该图其他各顶点(称为终点)有无路径?最短路径是什么?路径长为多少?问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。对邻接矩阵arsc[n][n]中的每一个元素只能有三种情况:①当i=j 时,p[i][j]=0; ②当顶点i到j无边时,p[i][j]= MAX; ③当顶点i到j 有边且权值为arcs[i][j]时,p[i][j]= arcs[i][j].
建立图的表示模块,顶点的插入和删除操作模块;在建立图之后从单源点开始求最短路径,并显示出来!
流程图如图4
Y
Y
N
N
建图
增加顶点
删除顶点
Dijkstra
算法
求最短路径
显示最短路径
输入顶点与边值信息
定义顶点个数
开始
结束

(2) 设计表示法
(1) 。
(2) 函数接口说明。
void ShortesPath(MGraph *G,int v0,int h)
int v,D[20],p[20][20],w,i,min,final[20],t=0;
char P[20][20];
char p1[2];
p1[1]='\0';
p1[0]=G->vexs[v0];
/* 求n个顶点,邻接矩阵为arcs,从源点v0到各顶点的最短路径,D[ ]记载从源点到其余各顶点的最短路径长度
, min=D [ ]为最短路径, 数组P[ ][ ]用来存储顶点,若P[v][w]为1,则w是从v0到v当前求的最短路径的顶点,final[v]为1当且仅当,即已求的从v0到v的最短路径。
(3)各部分的函数和各函数之间的关系
采用邻接矩阵表示法,构造有向图
typedef struct ell //定义顶点类型
typedef struct //定义图的类型
int LovateVex(MGraph *G,char v) //顶点定位函数
void Create(MGraph *G) 采用数组(邻接矩阵)表示法,构造无向网G.
void ShortesPath(MGraph *G,int v0,int h) 用Dijkstra算法