求解最短路径的Dijkstra算法.doc

一、问题分析与任务定义
本题主要是利用Dijkstra算法来求解顶点之间最短路径，其中包括如下几个待解决的问题：
1问题分析
选择合适的结构表示图主要包括：用Dijkstra算法实现起来更要容易；时间复杂度小；自己可以熟练应用。Dij-1;
for(j=0;jvn;j++)
if(s[j]==O&&dist[j]vmindis)
{
u=j;
mindis=dist[j];
}
s[u]=1;
for(j=O;jvn;j++)
if(s[j]==0)
if([u][j]vINF&&dist[u]+[u][j]vdist[j])
{
dist[j]=dist[u]+[u][j];
path[j]=u;
}
2采用邻接矩阵的存储结构
，和一个具有N个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点Vi的信息。
：
voidCreatdl(vexlistGV,adjmatrixGA,intn,inte)
{
intI,j,k,w;
coutvv输入vvnvv个顶点<<endl;
for(I=0;Ivn;I++)
cin>>GV[I];
for(I=0;Ivn;I++)
for(j=o;jvn;j++)
{if(I==j)
GA[I][j]=o;
else
GA[I][j]=MaxValue;
}
coutvv输入vvevv条边vvendl;
for(k=1;kv=e;k++)
{cin>>I>>j>>w;
GA[I][j]=GA[I][j]=w;
}
}
四、上机调试
对设计实现的回顾讨论和分析；算法的时、空性能分析和改进设想，经验和体会等。
调试中遇到的问题与解决方法
在进行输入输出语句的调试时，系统提示无法识别函数，>;
出现重大错误，多达数百条错误，着实郁闷了一阵；很多标点符号是在中文输入法状态下输入，造成系统无法识别，改掉后错误消失；如switch语句，在每条选择语句后，缺少break。，错误；
函数方法使用有误，无法通过；在赋实参时，对于变化的实参只需赋初值，子函数也可以调用子函数；
困惑很久的调用子函数问题，在赋实参时找不到实参;用switch语句进行相关选择代换，成功。
，int型与char型的替换上不知道用什么函数实现；
2设计体会
对C语言的使用不是很熟练，造成自己浪费很多时间在复****C语言，女口：结构体的使用，不能灵活应用do,while()，switch()语句等；调用子函数问题上，子函数之间错综复杂的调用和实参，形参的赋值让自己很是迷惑，三天时间，也许更多时间里，都是在研究怎样调用子函数。虽然最后基本是完成了教授布置下来的课程设计，但是还是有不尽人意的地方：结点的插入，删除，路径的实际化最终由于时间问题没能解决，很遗憾。程序缺乏人性化设计，估计第一次使用本程序的人会很迷茫。
3时间空间复杂度的计算
利用算法求解最短路径时，求每一对顶点之间的最短路径的一种方法是反复执行
次算法每次执行以一个顶点为源点求得从该顶点到其它各顶点的最短路径
其时间复杂度为。其空间的复杂度为o（n）。
五、用户使用说明
本程序主要是用来计算从某一点到其他各点的最短路径长度，第一次使用可能会有点迷茫，但是它却是本人两周来的血汗，如有不便请原谅。下面描述该使用方法：程序会在一开始让用户输入结点数，线路数，然后输入相关结点信息，有城市名字（只能使用英文名称），线路长度，起点城市，终点城市。接下来都由计算机完成。结果会输出源点到各城市间的长度。
六、测试结果输入数据：
输入城市数为：4
输入城市线路为：4
然后输入城市信息（这里每个数字彳
'弋表1A地
2B地3C地4D地）:
输入第一个城市信息：1
输入第一个城市信息：2
输入第二个城市信息：3
输入第四个城市信息：4
输入第一条线路的起点：
1，终点：
3
线路长度为＜KM＞：
56
输入第二条线路的起点：
2，终点：
3
线路长度为＜KM＞：
78
输入第三条线路的起点：
1，终点：
2
线路长度为＜KM＞：
89
输入第三条线路的起点：
3，终点：
4
线路长度为＜KM＞：
99
F面是结果截图:
F直每个数字代表一个城市，请输入相应的代码，第一个输入的是出发地
I-
・

二..右亠
134-
4::::也也必自心息息息BitHf:4曙B:乍乍朋乍也也鞋煨讀；rGj