东北大学秦皇岛分校
数据结构课程设计
交通咨询系统设计
专    业  计算机科学与技术
班    级 
姓    名
指导教师
日    期
                           
一、需求分析
设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。
本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。
1.1.1建立图的存储结构速度与激情6片头曲
邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵：
设G=（Vweightless，E）是一个图，结点集为。
G的邻接矩阵
当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。
图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：
#definf MVNum 50  //最大顶点数
typedef struct
      {   
  VertexType vexs[MVNum];        //顶点数组，类型假定为char型
  Adjmatrix arcs[MVNum][MVNum];  //邻接矩阵，假定为int型
}MGraph;
1.1.2 单源最短路径
最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望出从某个源点SV到G中其余各顶点的最短路径。
为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。
那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。
迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，，cost是表示G的邻接矩阵，cost[i][j]表示有向边<i,j>的权。若不存在有向边<i,j>，则cost[i][j]的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含一个元素，即顶点v1。数组dist记录从源点到其他顶点当前的最短距离，其初值为dist[i]=cost[v1][i],i=1,2,……,n。从S之外的顶点集合V-S中选出一个顶点w，使dist[w]的值最小。于是从源点到达w只通过S中顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到V-S为空。
最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i]表示从源点到顶点i之间的最短路径的前驱顶点。
因此，迪杰斯特拉算法可用自然语言描述如下：
初始化S和D，置空最短路径终点集，置初始的最短路径值；
S[v1]=TRUE;  D[v1]=0；    //S集初始时只有源点，源点到源点的距离为0；我不想说伴奏
While (S集中顶点数<n)
{
开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中；
S[v]=TRUE；
更新当前最短路径及距离；
}
1.1.3 任意一对顶点间最短路径
任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V，E），要对G中任意一对顶点有序对“v,w(vw)”,出v到w的最短路径。
要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。
这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。
费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点 vi到vj的最短路径。如果从vi到vj存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径<vi,v1>和<v1,vj>是否存在。如果存在，则比较<vi,vj>和< vi,v1,vj >的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径<vi,…,v2,…,vj>，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么<vi,…,v2,…,vj>可分解为<vi,…v2>和<v2,…,vj>,而这两条路径是前一次到的中间顶点序号不大于1的最短路径，将这两条路径长度相加就得到路径<vi,…,v2,…,vj>的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推，直到顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶
点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。
1.2 程序流程图
二、详细设计
2.1 建立有向图的存储结构   
void CreateMGraph(MGraph * G,int n,int e)
{
  int i,j,k,w;
  for(i=1;i<=n;i++)
  G->vexs[i]=(char)i;
  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  G->arcs[i][j]=Maxint;
  printf("输入%d条边的i,j及w:\n",e);
  for(k=1;k<=e;k++)
  {
    scanf("%d,%d,%d",&i,&j,&w);
    G->arcs[i][j]=w;
  }
    printf("有向图建立完毕\n");
}
2.2迪杰斯特拉算法
void Dijkstra(MGraph *G,int v1,int n)
{
int D2[MVNum],P2[MVNum];
int v,i,w,min;
enum boolean S[MVNum];
for(v=1;v<=n;v++)
  {
    S[v]=FALSE;
    D2[v]=G->arcs[v1][v];
    if(D2[v]<Maxint)
    P2[v]=v1;
    else
    P2[v]=0;
  }
D2[v1]=0;S[v1]=TRUE;
for(i=2;i<n;i++)
{
min=Maxint;
for(w=1;w<=n;w++)
if(!S[w]&&D2[w]<min)
  {
    v=w;min=D2[w];
  }
S[v]=TRUE;
for(w=1;w<=n;w++)梦想奇迹
阿信女朋友蛋蛋照片if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w]))
  {
    D2[w]=D2[v]+G->arcs[v][w];
    P2[w]=v;
  }
披着羊皮的狼 mp3
}
printf("路径长度  路径\n");