文档介绍：一、问题分析与任务定义
本题主要是利用Dijkstra算法来求解顶点之间最短路径,其中包括如下几个待解决的问题:
1 问题分析
选择合适的结构表示图主要包括:用Dijkstra算法实现起来更要容易;时间复杂度小;自己可以熟练应用。Dijstra算法的实现所应涉及到的各参数及变量:顶点的编号;各边权的初使化;如何求出从顶点到其他各点的最短距离;最短距离长度的求取等问题。
2 任务定义
对任意图,选择合适的数据结构表示图,在此基础上实现求解最短路径的Dijkstra算法。要求:对所设计的图的数据结构,提供必要的基本功能。
在带权的有向图中源点到终点的多条路径中寻找出一条各边权植之和最小的路径,即最短路径。
对任务的理解考虑设计的图结构是否具备必要的基本功能,具有实际的应用;图的邻接矩阵如何实现交互式;如何将输入的邻接矩阵溶入到dijstra 算法中去。需要解决什么样的实际问题。并且能够将程序与实际问题相结合,能够处理一般的最短路径问题。
二、概要设计和数据结构的选择
按路径长度递增的顺序产生最短路径。通过以上对问题的分析和任务的理解,设计出一个大体的模块和程序流程。
1程序中涉及到的结构体及子函数:
:
本程序设计使用了以下结构体:
struct vertex
{ int num; //顶点编号
int data; //顶点信息
}; //顶点类型
typedef struct graph
{
int n; //图中顶点个数
int e; //图中边的个数
struct vertex vexs[MAXVEX]; //顶点集合
int edges[MAXVEX][MAXVEX]; //边的集合
}AdjMaxix; //图的邻接矩阵类型
:
设计本程序需分成几个模块,要用到以下几个子函数:
AdjMaxix creatmgraph() //通过用户交互产生一个有向图的邻接矩阵;
void dispmgraph(AdjMaxix adj)//用于输出一个有向图的邻接矩阵;
void ppath(int path[],int i,int v0);
//选择输出一条最短路径
void DisPath(int dist[],int path[],int s[],int n,int v0)
//用path计算最短路径
void Dijkstra(AdjMaxix g,int v0) // Dijkstra算法
void change(int num) //用于替换顶点编号
ppath
main
DisPath
Dijkstra
change creatmgraph
creatmgraph
dispmgraph creatmgraph
图1 结构图
流程图
输入语句,cin>>n>>e;
cin>>b>>t>>w;
Dijkstra算法
dist[i]=[v0][i];s[i]=0;if([v0][i]<INF) path[i]=v0;else path[i]=-1;
s[v0]=1;path[v0]=0;把源点放入s中;
for(i=0;i<n;i++)
dist[j]=dist[u]+[u][j];得出最短路径;
path[j]=u;
Do{} while(x!='n');
if(i>=n);
if(j>=n)
结束
开始
yes
no
yes
图2 程序流程图
三、详细设计和编码
这里设计用邻接矩阵解决实际生活中城市间往返最短路径问题。
1 算法思想
把图中顶点集合分成两组,第一组为集合S,存放已求出其最短路径的顶点,第二组为尚未确定最短路径的顶点集合是V-S(用U表示),其中V为网中所有顶点集合。在这里我们设计一个有向图G=(V,E)为G地区的交通图。
,V=(1,2,……,N)代表各个城市。edges是表示G的邻接矩阵,edges[I][j]表示有向边<i,j>的权,这里的权值代表城市间距离。若不存在有向边<i,j>的权,则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中