《最短权路径》由会员分享，可在线阅读，更多相关《最短权路径（7页珍藏版）》请在金锄头文库上搜索。
1、最短权路径用于计算一个节点到其他所有节点最短路径。主要特点是以任一起始点为原点，沿权值最小的路径向其它节点扩展，直到将全部节点包含进最小路径集。基本思想已知图G=（V，E），我们希望找出从某任一结点ViV到V中的每个结点的最短路径。先任取一点V0，选择V0到周边各点中最短路径的一点V1，将d(V0,V1)加入最短路径集d(S)，V1加入点集S，然后选择V1到周边各点中最短路径1的一点V2，将d(V0,V2)加入最短路径集d(S)，V2加入点集S，如此不断将新点和最短路径加入点集和最短路径集，直到Vk只有到点集S=V0，V1，Vk-1，Vk的路径，这时将Vk-1选作起点，看有没有到除去点集S=V
2、0，V1，Vk-1，Vk其他点的最短路径，如果有将d(Vk-1,Vk+1)加入最短路径集d(S)，Vk+1加入点集S，如果没有选择Vk-2作为起点，再看有没有到除去点集S=V0，V1，Vk-1，Vk其他点的最短路径，如此反复，直到S点集包含全部点并且最后一条路径是从点集V0，V1，Vn-1，Vn到V0，V1，Vn-1，Vn。任意两点Vi, Vj最短权路径取最短路径集两点所经过点的最短路径和与两点直接路径的最小值即D(Vi, Vj)=min，d(Vi, Vj)举例一公司在六个城市c1，c2，c6中的每一个都有分公司。从ci到cj的班机旅费由下列矩阵中的第i行第j列元素给出(表示没有直接班机)：0
3、 30 2 0 815 0 70 4 0 10 18 0最短权路径测试程序代码：#include #include typedef char DataType;#define MaxSize 10#define MaxVertices 10#define MaxWeight 10000#include SeqList.h#include AdjMGraph.h#include WangJian.hvoid main(void)AdjMGraph g;char a=A,B,C,D,E,F;RowColWeight rcw=0,2,5,0,3,30,1,0,2,1,4,8,2,1,15,2,5,7
4、,4,3,4,5,3,10,5,4,18;int i,n=6,e=9;int distance6,path6;CreatGraph(&g,a,n,rcw,e);WangJian(g,0,distance,path);for(i=0;in;i+)printf(到顶点%c的最短距离为%dn,g.Vertices.listi,distancei);printf(从顶点%c到其他各顶点最短路径的前一顶点为:n,g.Vertices.list0);for(i=0;isize=0;int ListLength(SeqList L)return L.size;int ListInsert(SeqList *
5、L,int i,DataType x)int j;if(L-size=MaxSize)printf(顺序表已满无法插入!n);return 0;else if(iL-size)printf(参数i不合法!n);return 0;elsefor(j=L-size;ji;j-) L-listj=L-listj-1;L-listi=x;L-size+;return 1;int ListDelete(SeqList *L,int i,DataType *x)int j;if(L-size=0)printf(顺序表已空无数据元素可删!n);return 0;else if(iL-size-1)print
6、f(参数i不合法);return 0;else*x=L-listi;for(j=i+1;jsize-1;j+) L-listj-1=L-listj;L-size-;return 1;int ListGet(SeqList L,int i,DataType *x)if(iL.size-1)printf(参数i不合法!n);return 0;else *x=L.listi;return 1;包含的邻接表的头文件程序代码：#ifndef _SeqList_H#define _SeqList_H#endiftypedef structSeqList Vertices;int edgeMaxVertic
7、esMaxVertices;int numOfEdges; AdjMGraph;void Initiate(AdjMGraph *G,int n)int i,j;for(i=0;in;i+)for(j=0;jedgeij=0;else G-edgeij=MaxWeight;G-numOfEdges=0;ListInitiate(&G-Vertices);void InsertVertex(AdjMGraph *G, DataType vertex)ListInsert(&G-Vertices,G-Vertices.size,vertex);void InsertEdge(AdjMGraph *
8、G,int v1,int v2,int weight)if(v1G-Vertices.size|v2G-Vertices.size)printf(参数v1或v2越界出错!n);return;G-edgev1v2=weight;G-numOfEdges+;void DeleteEdge(AdjMGraph *G,int v1,int v2)if(v1G-Vertices.size | v2G-Vertices.size | v1=v2)printf(参数v1或v2越界出错!n);return;G-edgev1v2=MaxWeight;G-numOfEdges-;int GetFirstVex(A
9、djMGraph G,int v)int col;if(vG.Vertices.size)printf(参数v1越界出错!n);return -1;for(col=0;col0& G.edgevcolMaxWeight) return col;return -1;int GetNextVex(AdjMGraph G,int v1,int v2)int col;if(v1G.Vertices.size|v2G.Vertices.size)printf(参数v1或v2越界出错!n);return -1;for(col=v2+1;col0&G.edgev1colMaxWeight) return c
10、ol;return -1;typedef structint row;int col;int weight;RowColWeight;void CreatGraph(AdjMGraph *G,DataType V,int n,RowColWeight E,int e)int i,k;Initiate(G,n);for(i=0;in;i+)InsertVertex(G,Vi);for(k=0;ke;k+)InsertEdge(G,Ek.row,Ek.col,Ek.weight);包含的最短权路径程序头文件代码：void WangJian(AdjMGraph G,int v0,int distan
11、ce,int path)int n=G.Vertices.size;int *s=(int*)malloc(sizeof(int)*n);int minDis,i,j,u,k;for(i=0;in;i+)distancei=G.edgev0i;si=0;if(i!=v0&distanceiMaxWeight) pathi=v0;else pathi=-1;sv0=1;for(i=1;in;i+)if(si) i+;minDis=MaxWeight; for(j=1;jn;j+)if(sj=0&distancejminDis) u=j;minDis=distancej;if(minDis=MaxWeight)return;su=1; for(k=1;kn;k+) if(sk=1&G.edgeukMaxWeigh
