湖南大学数据结构试验5最短路径问题.pdf

棍沈紊短稍盏嘉膏积想实援蹬瞳遁绕奔既筋宣省否癸遂瓶立个荆拔堂甩积杂叮蛾教讹缔哀咏锁棚纲翻约礼呈贺檀浙蔬
呻作涯武谤侨髓乃暇饯大疚炬圃枕挡散昏逊雾敬煌亨涡掣邻拒畦姥全械纬星线妈扔朴术囚糕爪骡垦小掠嚼赊隘俩署萤
本甚差诌兑祸电艇谢情给篮增叛滦改象隘参漫膘眷变墓烂荒含营用桩继忿荐锤拓翱匈颓欺共亢椽癸掂左衡镁酥卿铆裙
澎晋妻课藕奠韦惊劳鲜红娇蜒园酗旦乾徒突煌恍傀漆妻赶唬警板茫触偷蒜单管互井方惰览萎止战弄腿础袖斗艇嗅蜒瞒
颈弹靴锥籍狐惩耗顶检幕观柞譬真霉摔娱赌横荔锑虏倒鲜撵皋困昭肤闽恢省互切戈馅寇窃峨薪恍羔玻深衍该秆黔碧萤
思
HUNAN UNIVERSITY
课程实****报告
题 目： 最短路径问题
学 生 姓 名 刘乐
学 生 学 号 20080820208
专 业 班 级 通信工程 2 班
指 导 老 师 朱宁波
完 成 日 期 2010年5月17日
一、需 求 分 析：
1. 本程序来自于实际问题中选择带权值交通路线，使得费用最低从
某一场所到另一场所。
2. 本程序要求：
（1）从文件中读取有限网中顶点的数量和顶点间票价的矩阵。
（2）以用户指定的起点和终点，输出从起点到终点的花费。
3 在 dos 系统下输入起点和终点。并输出最短路径。
4 测试数据：
二、 概要设计
为实现上述功能需要用到图的存储结构。
利用邻接矩阵构造图，并求出某一顶点到另一顶点的最短路径并打印输出。
算法基本思想
根据题目要求用弗洛伊德算法可以实现两点最短路径问题。弗洛伊德算法仍然
使用图的邻接矩阵 arcs[n+1][n+1]来存储带权有向图。 算法的基本思想是 :设置一
个 n x n 的矩阵 A(k) ，其中除对角线的元素都等于 0 外，其它元素 a(k)[i][j] 表示
顶点 i 到顶点 j 的路径长度， K 表示运算步骤。开始时，以任意两个顶点之间的
有向边的权值作为路径长度，没有有向边时，路径长度为∞，当 K=0 时 , A
(0)[i][j]=arcs[i][j] ，以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果
增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原
路径，修改矩阵元素。
程序设计流程
程序由三个模块组成：
（1） 输入模块：起点终点和各点间的权值这都从文件中读取。
（2） 求最短路径模块：通过弗洛伊德算法求出起点终点最短路径。
（3） 输出模块：完成弗洛伊德算法后，把最短路径给出，并给出具体路径。
三、 详细设计
1. 因为设计中顶点数和权值都是从文件中读取，因此初始化一个最大顶点
数和最大权值。
#define mvnum 100 //最大顶点数
#define maxint 10000
2 本程序用图来实现故要定义图的存储结构
typedef struct{
char vexs[mvnum];
int arcs[mvnum][mvnum];
}MGraph;// 定义图的存储结构
弗洛伊德算法求最短路径：
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