最短路径（链路状态）.docx

最短权路径 用于计算一个节点到其他所有节点最短路径。主要特点是以任一起始点为原点，沿权值最小的路径向其它节点扩展，直到将全部节点包含进最小路径集。 基本思想 已知图?G=（V，E），我们希望找出从某任一结点Vi∈V到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={V0，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 　∞ 　　５?　　　30 　∞　　∞ 2 　0 　　∞ 　　　∞ 　　8?　　∞ ∞?　15 　　0 　　　∞　　∞ 　　7 ∞　∞　　　∞　　　0　　∞　　　∞ ∞ 　∞?　　∞　　　4 　　0　　 ∞ ∞ 　∞ 　　∞?　　10 　　18　　 0 最短权路径测试程序代码： #include stdio.h #include malloc.h typedef char DataType; #define MaxSize 10 #define MaxVertices 10 #define MaxWeight 10000 #include SeqList.h #include AdjMGraph.h #include WangJian.h void 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,3,4},{5,3,10},{5,4,18}}; int i,n=6,e=9; int distance[6],path[6]; CreatGraph(g,a,n,rcw,e); WangJian(g,0,distance,path); for(i=0;in;i++) printf(到顶点%c的最短距离为%d\n,g.Vertices.list[i],distance[i]); printf(从顶点%c到其他各顶点最短路径的前一顶点为:\n,g.Vertices.list[0]); for(i=0;in;i++) if(path[i]!=-1) printf(到顶点%c的前一顶点为%c\n,g.Vertices.list[i],g.Vertices.list[path[i]]); } 包含的顺序表的头文件代码： #define MaxSize 10 #define MaxVertices 10 #define MaxWeight 10000 typedef char DataType; typedef struct { DataType list[MaxSize]; int size; } SeqList; void ListInitiate(SeqList *L) { L-size=0; } int ListLength(SeqList L) { return L.size; } int ListInsert(SeqList *L,int i,DataType x) { int j; if(L-size=MaxSize) { printf(顺序表已满无法插入!\n); return 0; } else if(i0||iL-size) { printf(参数i不合法!\n); return 0; } else { for(j=L-size;ji;j--) L-list[j]=L-list[j-1]; L-list[i]=x; L-size++; return 1; } } int