单源结点最短路径

单源结点最短路径一、题目单源结点最短路径问题。二、问题描述求从有向图的某一结点出发到其余各结点的最短路径。三、基本要求（1）有向图采用邻接矩阵表示。（2）单源结点的最短路径问题采用狄克斯特拉算法。（3）输出有向图中从源结点到其余各结点的最短路径和最短路径值。四、测试数据测试数据为如下图所示的有向带权图，以结点v1作为源结点，求从结点v1到其余各结点的最短路径和最短路径的长度值。图有向带权图五、算法思想1.算法流程图算法流程图（2）算法分析按已给有向图构造出图G结构体，顺序表存储顶点信息，矩阵存储邻接矩阵信息，记录边的条数；选择v1为起始顶点，用狄克斯特拉算法求v1顶点到其他各个顶点的最短路径值和最短距离。将所有的顶点分为S、T两类，S用来存放已知最短路径的顶点。而T存放未知最短路径的顶点。如果起始点（v1）到某个相邻顶点的最短距离已经求出，比如v1-v2的距离。那么就把v2归入S，其余的不能直接算出最短距离的则要归入T。刚开始的S只有起始点一个，随着算法的继续，首先将起始点相邻的点归入到S，知道最后一个顶点归入S。六、模块划分1.创建图（1）算法流程创建图流程（2）求得G图结构如下图所示：顺序表V1V2V3V4V5V601020708120342516012100邻接矩阵边的条数:112.求最短路径和最短距离算法流程图（1）求得最短距离矩阵如下111520143520113520111120111110111110]6][6[path（2）求得最短距离矩阵如下20292212100]6[distance七、数据结构1.结构体定义（1）图的结构体定义typedefstruct{SeqListVertices;//存放顶点的顺序表intedge[MaxVertices][MaxVertices];//存放边的邻接矩阵intnumOfEdges;//边的条数}AdjMGraph;//图的结构体定义（2）边信息结构体定义typedefstruct{introw;//行下标intcol;//列下标intweight;//权值}RowColWeight;//边信息结构体定义八、源程序1.子函数AdjMGraph.h/**邻接矩阵存储存储结构下图操作的实现**/#ifndefADJMGRAPH_H_INCLUDED#defineADJMGRAPH_H_INCLUDED#includeSeqList.h//包含顺序表头文件typedefstruct{SeqListVertices;//存放顶点的顺序表intedge[MaxVertices][MaxVertices];//存放边的邻接矩阵intnumOfEdges;//边的条数}AdjMGraph;//图的结构体定义/**初始化有n个顶点的顶点顺序表和邻接矩阵**/voidInitiate(AdjMGraph*G,intn){inti,j;for(i=0;in;i++)for(j=0;jn;j++){if(i==j)G-edge[i][j]=0;elseG-edge[i][j]=MaxWeight;//MaxWeight表示无穷大}G-numOfEdges=0;//边的条数置为0ListInitiate(&G-Vertices);//顺序表初始化}/**在图中增加一个顶点**/voidInsertVertex(AdjMGraph*G,DataTypevertex)//在图中插入顶点vertex{ListInsert(&G-Vertices,G-Vertices.size,vertex);//顺序表尾插入}/**在图中增加一条有向边**/voidInsertEdge(AdjMGraph*G,intv1,intv2,intweight)//在图G中插入边v1,v2，边v1,v2的权为weight{if(v10||v1=G-Vertices.size||v20||v2=G-Vertices.size){printf(参数v1或v2越界出错！\n);return;}G-edge[v1][v2]=weight;G-numOfEdges++;}/**在图中取消一条有向边**/voidDeleteEdge(AdjMGraph*G,intv1,intv2)//在图G中删除边v1,v2{if(v10||v1=G-Vertices.size||v20||v2=G-Vertices.size||v1==v2){printf(参数v1或v2出错\n);return;}if(G-edge[v1][v2]==MaxWeight||v1==v2){printf(该边不存在！\n);return;}G-edge[v1][v2]=MaxWeight;G-numOfEdges--;}/**取第一个邻接顶点**/intGetFirstVex(AdjMGraphG,intv)//在图G中需要序号为V的顶点的第一个邻接顶点//如果这样的邻接顶点存在，则返回该邻接顶点的序号，否则返回-1{intcol;if(v0||v=G.Vertices.size){printf(参数v1越界！\n);return-1;}for(col=0;colG.Vertices.size;col++)if(G.edge[v][col]0&&G.edge[v][col]MaxWeight)returncol;return-1;}/**取下一个邻接顶点**/intGetNextVex(AdjMGraphG,intv1,intv2)//在图G中寻找V1顶点的邻接顶点V2的下一个邻接顶点{intcol;if(v10||v1=G.Vertices.size||v20||v2=G.Vertices.size){printf(参数v1或v2越界出错！\n);return-1;}for(col=v2+1;colG.Vertices.size;col++)if(G.edge[v1][col]0&&G.edge[v1][col]MaxWeight)returncol;return-1;}#endif//ADJMGRAPH_H_INCLUDED2.子函数AdjMGraphCreate.h/**图的创建函数**/#ifndefADJMGRAPHCREATE_H_INCLUDED#defineADJMGRAPHCREATE_H_INCLUDEDtypedefstruct{introw;//行下标intcol;//列下标intweight;//权值}RowColWeight;//边信息结构体定义voidCreatGraph(AdjMGraph*G,DataTypeV[],intn,RowColWeightE[],inte)//在图G中出入n个顶点信息V和e条边的信息E{inti,k;Initiate(G,n);//顶点顺序表初始化for(i=0;in;i++)InsertVertex(G,V[i]);//插入顶点for(k=0;ke;k++)InsertEdge(G,E[k].row,E[k].col,E[k].weight);//插入边}#endif//ADJMGRAPHCREATE_H_INCLUDED3.子函数Dijkstra.h#ifndefDIJKSTRA_H_INCLUDED#defineDIJKSTRA_H_INCLUDED#defineN6voidDijkstra(AdjMGraphG,intv1,intdistance[],intpath[][N])//带权图G从下标v1顶点到其他顶点的最短距离distance和最短路径下标path{intn=G.Vertices.size;int*s=(int*)malloc(sizeof(int)*n);intminDis,i,j,u,k;//初始化for(i=0;in;i++){path[i][0]=v1;for(j=1;jn;j++)path[i][j]=-1;}for(i=0;in;i++){distance[i]=G.edge[v1][i];s[i]=0;if(i!=v1&&distance[i]MaxWeight)path[i][1]=i;}//标记顶点v0已从集合T加入到集合S中s[v1]=1;//在当前还未找到最短路径的顶点集中选取具有最短距离的顶点ufor(i=1;in;i++){minDis=MaxWeight;for(j=0;jn;j++)if(s[j]==0&&distance[j]minDis){u=j;minDis=distance[j];}//当已不存在路径时，算法结束。此句对非连通图是必需的if(minDis==MaxWeight)return;//标记顶点u已从集合T加入到集合S中s[u]=1;//修改从v0到其他顶点的最短路径和最短距离for(j=0;jn;j++){if(s[j]==0&&G.edge[u][j]MaxWeight&&distance[u]+G.edge[u][j]distance[j]){//顶点v0经顶点U到其他顶点的最短距离和最短路径distance[j]=distance[u]+G.edge[u][j];for(k=0;path[u][k]!=-1;k++){path[j][k]=path[u][k];}path[j][k++]=j;path[j][k]=-1;}}}}#endif//DIJKSTRA_H_INCLUDED4.子函数SeqList.h#ifndefSeqList_H#defineSeqList_Htypedefstruct{DataTypelist[MaxSize];//DataType这个在你用的时候可以去定义它的类型intsize;//指这个表的总长度}SeqList;//定义抽象数据类型SeqListvoidListInitiate(SeqList*L)//初始化顺序表L{L-size=0;//定义初始元素个数}intListLength(SeqListL){returnL.size;}intListInsert(SeqList*L,inti,DataTypex)//在顺序表L的位置i（0=i=size为当前数据元素个数）插入数据元素值x//插入成功返回1，否则返回0{intj;if(L-size=MaxSize){printf(表已满无法插入！\n);return0;}elseif(i0||iL-size){printf(参数i不合法！\n);return0;}else{for(j=L-size;ji;j--){L-list[j]=L-list[j-1];}L-list[i]=x;L-size++;return1;}}intListDelete(SeqList*L,inti,DataType*x)//删除顺序表L中位置i上的数据元素并保存到x中//插入成功返回1，否则返回0{intj;if(L-size=0){printf(表已空无法插入！\n);return0;}elseif(i=0||iL-size-1){printf(参数i不合法！\n);return0;}else{*x=L-list[i];for(j=i+1;j=L-size-1;j++)L-list[j-1]=L-list[j];L-size--;return1;}}intListGet(SeqListL,inti,DataType*x)//取顺序表L中第i个元素的值，取到则返回1，否则返回0{if(i0||iL.size-1){printf(参数i不合法！\n);return0;}else{*x=L.list[i];return1;}}intLis