完整word版数据结构课程设计-城市最短路径求解.doc

(完整word版)数据结构课程设计_城市最短路径求解
(完整word版)数据结构课程设计_城市最短路径求解

(完整word版)数据结构课程设计_城市最短路径求解
数据结构课程设计
—省会城市最短路径求解
一、类关系图

说明：Graph类继承Form类，同时嵌入了CityInf结构体和List类。
Graph类的几个重要函数、类、结构体
privatevoidInit()//初始化函数
privatevoidShowMap_Paint(objectsender,PaintEventArgse)//绘制地图
privateboolGetMinDistanceFun(intentry)//采用迪杰斯特拉算法获得最短路径
privatevoidBFS(intStartPoint,int[]visited,stringname)//广度优先遍历函数
privatevoidDFS(intStartPoint,int[]visited,stringname)//深度优先遍历函数
privatevoidPrim()//求解最小生成树Prim算法
privateclassList//广度优先遍历用到的队列类
publicstructCityInf//存放城市信息：城市名称、城市坐标、状态值

二、流程图
主界面
路径
增删
应用
设置
求最短路径
仅显示最短路径
显示或隐藏距离数据
显示全部城市到起点城市的最短路径
随机产生路径
最小生成树
删除两个城市之间的路
增加两个城市之间的路
深度优先遍历
最短距离
广度优先遍历
寻径过程
选择文件
查看邻接矩阵(在模拟数据中)
模拟数据
城市数据
真实地图

三、主要算法的实现
1．用迪杰斯特拉算法实现省会城市间最短路径的求解
privateboolGetMinDistanceFun(intentry)
{
intinputnodenum=CityData.citysum;
int[]Mark=newint[inputnodenum]; //标志位数组标记数据在哪个集合
intmindis=0,nextnode=0;//最短路径，下一个城市结点
inti,j;
//第一轮距离数组记录从起始点到其他所有点的边权值
for(i=0;i<inputnodenum;i++)
{
Distance[i]=GetCityWeight(entry,i);
//所有标志位清零
Mark[i]=0;
//如果起始结点可以抵达某个结点
if(i!=entry&&Distance[i]<MaxWeight)
{
RoutePath[i]=entry;//则把该结点首先放入路径数组
}
else
{
RoutePath[i]=-1;//表示该路径不通
}
}
//初始状态下集合存放找到最短路径顶点集合的中只包含源点entry所以把它在Mark中标记出来
Mark[entry]=1;
//在还没有找到最短路径的结点集合中选取最短距离结点nextnode
for(i=1;i<inputnodenum;i++)
{
//设定每轮的初始最小距离为无穷大
mindis=MaxWeight;
for(j=0;j<inputnodenum;j++)
{
//保证每次循环mindis是到entry的最小值
if(Mark[j]==0&&Distance[j]<mindis)//如果没有进入最短路径且距离小于最小距离
{
nextnode=j;
mindis=Distance[j];//记录本次循环的最短路径
}
}

if(mindis==MaxWeight)//不存在最短路径退出
{
returnfalse;
}
//把nexinode在集合mark中标记成已在最短路径集合中
Mark[nextnode]=1;
//每加入一个元素都要修改entry到最短路径集合都要再修改entry到剩余顶点的最短路径长度值
for(j=0;j<inputnodenum;j++)//修改结点v0到其他的结点最短的距离
{
//找到新的最短路径
if(Mark[j]==0&&GetCityWeight(nextnode,j)<MaxWeight
&&Distance[nextnode]+GetCityWeight(nextnode,j)<Distance[j])
{
//新的最短路径
Distance[j]=Distance[nextnode]+GetCityWeight(nextnode,j);
//把该点加入路径
RoutePath[j]=nextnode;
}
}
}
returntrue;
}2.Prim算法实现全国公路网最小生成树的求解
privatevoidPrim()
{
inti=0,j=0,k=0;
//权值数组保存权值的数