论文部分内容阅读
摘要：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Dijkstra算法。对所设计的图的数据结构，提供必要的基本功能。建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径并显示。实现的功能有建立有向图，排除和增加目的地，方便找出最短路径，在建立好的有向图中，显示出来从顶点到各个顶点的最短路径。
关键词：最短路径；有向图；数据结构
中图分类号：TP313文献标识码：A文章编号：1009-3044(2012)12-2759-03
1设计问题的提出
1.1对于最短路径问题
最短路径是在实际应用中非常有用的工具，将该问题细分，可以分为点到点最短路径，单源点的最短路径，所有点到所有点以及带负边情况下的最短路径。
1.2 Dijkstra算法的主要思想
Dijkstra算法的基本思路是：假设每个点都有一对标号(dj, pj)，其中dj是从起源点s到点j的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
1)初始化。起源点设置为：①ds=0, ps为空;②所有其他点: di=∞, pi=;③标记起源点s，记k=s,其他所有点设为未标记的。
2)检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：dj=min［dj, dk lkj］式中，lkj是从点k到j的直接连接距离。
3)选取下一个点。从所有未标记的结点中，选取dj中最小的一个i：di=min［dj,所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。
4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j* 5)标记点i。如果所有点已标记，则算法完全退出，否则，记k=i，转到2)再继续。
2概要设计
在任意图中实现求最短路径问题,首先是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径，所以，建立图这一步很关键。在实际使用当中，顶点的信息是成千上万，而且是随时可能产生变动，故建图模块要实现顶点的删除和插入操作；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能，这也是程序实际化的要求。
3建图过程
能把一个带有顶点和权值的数据结构图输入电脑首先要用到数组，存储每个顶点信息以及每两个顶点构成的线路的权值。在建图的过程中，图的信息不是一成不变的，所以在实现初步输入图的信息后，要有删除和插入操作。需要插入顶点的时候，回归到初始建图模块，但是这个操作是在已建立的图上操作，而非在清除内存之后进行插入，所以，要实现插入的高效和实用性。在删除顶点的时候，在已建立的图上进行删除，首先对图进行遍历，只要是和欲删除的顶点有关联的边值都要删除掉，这样就实现了顶点的删除操作，目的是提高用户使用程序的效率，对已知或者误录入的顶点进行排除，增加了程序的人性化。
4 Dijkstra求最短路径的基本思想
把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v1到其它各顶点间的最短路径,则在任意时刻，从v1到第一组各顶点间的最短路径都不大于从v1到第二组各顶点间的最短路径。
4.1 Dijkstra求最短路径的步骤
设图以邻接矩阵cost存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权值用无穷大表示。从顶点v1到其它各顶点间的最短路径的具体步骤如下：
1）初始化：s[MAX]。设一dist向量，其下标是各顶点，元素值是顶点v0到各顶点的边的权值。若v0到某顶点无边，dist向量中的对应值为无穷大。
2）选dist中最小的权值，将其顶点s[V0]加入s集合。
3）修改从顶点V0到集合s[MAX]中各顶点的最短路径长度,如果
dist[u] cost[u][j] 则修改dist[k]为
dist[k]=dist[u] cost[u][j]
4)重复（2）、（3）n-1次。由此求得v1到图上其余各顶点得最短路径。
4.2存储结构体：用于存储经过的顶点和顶点数以及权值
struct
{int num;
int pnode[MAX]; }path[MAX]; //path为从V0到各顶点的最短路径
4.3建图子函数：
void creatgraph()//创建带权有向图
{ int i,j,s,e,len,contin=1;
printf("请输入点个数:");
scanf("%d",
关键词：最短路径；有向图；数据结构
中图分类号：TP313文献标识码：A文章编号：1009-3044(2012)12-2759-03
1设计问题的提出
1.1对于最短路径问题
最短路径是在实际应用中非常有用的工具，将该问题细分，可以分为点到点最短路径，单源点的最短路径，所有点到所有点以及带负边情况下的最短路径。
1.2 Dijkstra算法的主要思想
Dijkstra算法的基本思路是：假设每个点都有一对标号(dj, pj)，其中dj是从起源点s到点j的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
1)初始化。起源点设置为：①ds=0, ps为空;②所有其他点: di=∞, pi=;③标记起源点s，记k=s,其他所有点设为未标记的。
2)检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：dj=min［dj, dk lkj］式中，lkj是从点k到j的直接连接距离。
3)选取下一个点。从所有未标记的结点中，选取dj中最小的一个i：di=min［dj,所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。
4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j* 5)标记点i。如果所有点已标记，则算法完全退出，否则，记k=i，转到2)再继续。
2概要设计
在任意图中实现求最短路径问题,首先是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径，所以，建立图这一步很关键。在实际使用当中，顶点的信息是成千上万，而且是随时可能产生变动，故建图模块要实现顶点的删除和插入操作；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能，这也是程序实际化的要求。
3建图过程
能把一个带有顶点和权值的数据结构图输入电脑首先要用到数组，存储每个顶点信息以及每两个顶点构成的线路的权值。在建图的过程中，图的信息不是一成不变的，所以在实现初步输入图的信息后，要有删除和插入操作。需要插入顶点的时候，回归到初始建图模块，但是这个操作是在已建立的图上操作，而非在清除内存之后进行插入，所以，要实现插入的高效和实用性。在删除顶点的时候，在已建立的图上进行删除，首先对图进行遍历，只要是和欲删除的顶点有关联的边值都要删除掉，这样就实现了顶点的删除操作，目的是提高用户使用程序的效率，对已知或者误录入的顶点进行排除，增加了程序的人性化。
4 Dijkstra求最短路径的基本思想
把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v1到其它各顶点间的最短路径,则在任意时刻，从v1到第一组各顶点间的最短路径都不大于从v1到第二组各顶点间的最短路径。
4.1 Dijkstra求最短路径的步骤
设图以邻接矩阵cost存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权值用无穷大表示。从顶点v1到其它各顶点间的最短路径的具体步骤如下：
1）初始化：s[MAX]。设一dist向量，其下标是各顶点，元素值是顶点v0到各顶点的边的权值。若v0到某顶点无边，dist向量中的对应值为无穷大。
2）选dist中最小的权值，将其顶点s[V0]加入s集合。
3）修改从顶点V0到集合s[MAX]中各顶点的最短路径长度,如果
dist[u] cost[u][j]
dist[k]=dist[u] cost[u][j]
4)重复（2）、（3）n-1次。由此求得v1到图上其余各顶点得最短路径。
4.2存储结构体：用于存储经过的顶点和顶点数以及权值
struct
{int num;
int pnode[MAX]; }path[MAX]; //path为从V0到各顶点的最短路径
4.3建图子函数：
void creatgraph()//创建带权有向图
{ int i,j,s,e,len,contin=1;
printf("请输入点个数:");
scanf("%d",