最短路径算法.docx

最短距离算法(Dijkstra )设计与编程实现
所在系
（院）:
业:
级:
号:
名:
随着知识经济的到来，信息将成为人类间距离。若不存在 有向边vi,j＞的权，贝U edges[I][j]的权为无穷大（可取值为INF=32570 ）。设S 为一个集合，其中的每个元素表示一个城市，求出从源点（自定义）城市到这些 顶点城市的最短距离。S的初态只包含顶点V0。数组dist记录从V0到其他各城 市当前的最短距离，其初值dist[I]=edges[V0][I]。从S之外的顶点集合V-S中 选出一个城市u。使dist[w]的值最小。于是从源点到达 u只通过S中的城市， 把u加入集合S中调整dist中记录的从源点到V-S中每个城市V的距离：从原 来的dist[v]和dist[w]+edges[w][v] 中选择较小的值作为新的 dist[v]。重复上述
过程，直到S中包含V中其余顶点的最短路径。
void Dijkstra(AdjMaxix g,i nt vO)
{int dist[MAXVEX], path[MAXVEX]; int s[MAXVEX];
int mi ndis,i,j,u, n=; for(i=0;i< n;i++)
{
dist[i]=[v0][i]; s[i]=0;
if([v0][i]vlNF)
p ath[i]=v0;
else
path[i]=-1;
}
s[vO]=1; path[vO]=O;
for(i=0;iv n;i++)
{
mindis=INF;
u=-1;
for(j=0;j<n;j++)
if(s[j]==0 && dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
s[u]=1;
for(j=0;j<n;j++)
if(s[j]==0)
if([u][j]<INF&&dist[u]+[u][j]<dist[j])
{
dist[j]=dist[u]+[u][j];
path[j]=u;
}
采用邻接矩阵的存储结构
基本概念
图的邻接矩阵可以使用一个二维数组存储顶点之间相邻关系的邻接矩阵， 和 一个具有 N 个元素的一维数组存储顶点信息，其中下标为 i 的元素存储顶点 Vi 的信息。
算法描述
void Creatdl(vexlist GV ,adjmatrix GA,int n,int e) {
int I,j,k,w;
cout<< ”输入” <<n<< ”个顶点 ” <<endl; for(I=0;I<n;I++)
cin>>GV[I];
for(I=0;I<n;I++)
for(j=o;j<n;j++)
{if(I==j)
GA[I][j]=o;
else
GA[I][j]=MaxValue;
}
cout<< ”输入” <<e<< ”条边” <<endl;
for(k=1;k<=e;k++)
{cin>>I>>j>>w;
GA[I][j]=GA[I][j]=w;
}
}
4. 上机调试 对设计实现的回顾讨论和分析； 算法的时、 空性能分析和改进设想， 经验和 体会等。
调试中遇到的问题与解决方法
在进行输入输出语句的调试时，系统提示无法识别函数，缺少头文件
<>；
出现重大错误， 多达数百条错误， 着实郁闷了一阵； 很多标点符号是在中文 输入法状态下输入，造成系统无法识别，改掉后错误消失；如 switch 语句，在 每条选择语句后，缺少 break() ，错误；
函数方法使用有误，无法通过；在赋实参时，对于变化的实参只需赋初值， 子函数也可以调用子函数；
困惑很久的调用子函数问题，在赋实参时找不到实参；用 switch 语句进行 相关选择代换，成功。
连系实际问题上， int 型与 char 型的替换上不知道用什么函数实现；
设计体会
对C语言的使用不是很熟练，造成自己浪费很多时间在复习 C语言，女口：结 构体的使用，不能灵活应用 do,while( ) ， switch( ) 语句等；调用子函数问题
上，子函数之间错综复杂的调用和实参， 形参的赋值让自己很是迷惑， 三天时间， 也许更多时间里， 都是在研究怎样调用子函数。 虽然最后基本是完成了教授布置 下来的课程设计，但是还是有不尽人意的地方：结点的插入，删除，路径的实际 化最终由于时间问题没能解决， 很