数据结构课程设计
—省会城市最短路径求解一、类关系图
说明：Graph类继承Form类，同时嵌入了CityInf结构体和List类。
Graph类的几个重要函数、类、结构体
private void Init()//初始化函数
private void ShowMap_Paint(object sender, PaintEventArgs e) //绘制地图
private bool GetMinDistanceFun(int entry) //采用迪杰斯特拉算法获得最短路径private void BFS(int StartPoint, int[] visited, string name) //广度优先遍历函数private void DFS(int StartPoint, int[] visited, string name)//深度优先遍历函数private void Prim()//求解最小生成树 Prim算法
private class List //广度优先遍历用到的队列类
public struct CityInf//存放城市信息：城市名称、城市坐标、状态值
二、流程图
三、主要算法的实现
1．用迪杰斯特拉算法实现省会城市间最短路径的求解
private bool GetMinDistanceFun(int entry)
{
int inputnodenum = CityData.citysum;
int[] Mark = new int[inputnodenum]; //标志位数组标记数据在哪个集合
int mindis = 0, nextnode = 0;//最短路径，下一个城市结点
int i, 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)//不存在最短路径退出
{
return false;
}
//把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;
}
}
}
return true;
}
this.MinTreeEdges[i, j] = 0;
}
}
//辅助数组初始化权值数组赋值
for (i = 1; i < this.CityData.citysum; ++i)
{
WeightArrays[i] = this.Edges[0, i];
NodeArrays[i] = 0;
}
//某个顶点加入集合U
WeightArrays[0] = 0;
NodeArrays[0] = 0;
//判断最小的权值通过的顶点的循环就此开始
for (i = 0; i < this.CityData.citysum; ++i)
{
k = 1;
j = 1;
mincost = this.MaxWeight;
//选取权值最小的边和相应的顶点
while (j < this.CityData.citysum)
{
if (WeightArrays[j] < mincost && WeightArrays[j] != 0)
{
mincost = WeightArrays[j];
k = j;
}
j++;
}
//新顶点加入集合U
WeightArrays[k] = 0;
this.MinTreeEdges[k, NodeArrays[k]] = this.Edges[k, NodeArrays[k]];
this.MinTreeEdges[NodeArrays[k], k] = this.Edges[k, NodeArrays[k]];
//重新计算该顶点到其余顶点的边的权值
for (j = 1; j < this.CityData.citysum; j++)
{
if (this.Edges[k, j] < WeightArrays[j])
{
WeightArrays[j] = this.Edges[k, j];
NodeArrays[j] = k;
}
}
}
this.Default();
this.showmintree = true;
