资源描述
从某个源点到其它各顶点间的最短路径这里路径指两顶点间的通路，路径的长度指所有经过的边的总长。“最短路径”的问题指 当两个顶点间通路多于一条时，如何找出边长总和为最短的那条。Dijkstra提出按路径长度 递增的次序求最短路径的方法。1、Dijkstra 求最短路径的基本思想把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径 的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v0到其 它各顶点间的最短路径,则在任意时刻，从 v0 到第一组各顶点间的最短路径都不大于从 v0 到第二组各顶点间的最短路径。2、Dijkstra 求最短路径的步骤设图以邻接矩阵 arcs 存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权 值用无穷大表示。从顶点 v0 到其它各顶点间的最短路径的具体步骤如下：（1）初始化：第一组（集合s）只含顶点v0,第二组（集合v-s）含有图中其余顶点。 设一 dist向量，其下标是各顶点，元素值是顶点v0到各顶点的边的权值。若v0到某顶点无 边， dist 向量中的对应值为无穷大。（2）选dist中最小的权值，将其顶点（j）加入s集合。s=s j（3）修改从顶点v0到集合t（t=V-s）中各顶点的最短路径长度，如果 distj+arcsjk#include #define INFINITY INT_MAX#define MAXVEX 6#define FALSE 0#define TRUE 1typedef char VexType;typedef float AdjType;/* 图的顶点个数 */* 顶点信息 */* 边信息 */typedef struct int vexnum;VexType vexsMAXVEX;AdjType arcsMAXVEXMAXVEX;MGraph;void ShortestPath_DIJ(MGraph &G,int pMAXVEX,AdjType D) int v,w,i,j;AdjType min;int finalMAXVEX;finalv为TRUE当且仅当v u s,即已求得从v0到v的最短路径for(i=0;iG.vexnum;i+) finali=FALSE; Di=G.arcs0i;for(w=0;wG.vexnum;w+) piw=FALSE; /*设空路径*/ if(DivINFINITY)/*如果 V0 到 Vi 有直接路径则置 pi0和 pii为 1*/ pi0=TRUE;pii=TRUE;/*for语句结束*/D0=0; final0=TRUE;/*初始化，表示顶点v0在集合S中*/for(i=1;iG.vexnum;i+)/*开始主循环，每次求得v0到某个v顶点的最短路径，并加v到s集*/*在 V-S 中选出距离值最小顶点*/*w顶点离v0顶点是更近*/ min=INFINITY;for(w=0;wG.vexnum;w+) if(!finalw&Dwmin) v=w; min=Dw; finalv=TRUE; for(w=0;wG.vexnum;w+)/*离 v0 最近的 v 加入 S 集*/*更新当前最短路径及距离*/*修改 Dw和 pw, wUv-S*/*修改路径长度*/if(!finalw&(min+G.arcsvwDw) Dw=min+G.arcsvw;for(j=0;jvGvexnum;j+) pwj=pvj; /*修改路径为经过 v 到达 w*/ pww=TRUE; /*if 结束 */*for 结束*/ /*ShortestPath_DIJ 结束*/void main() int i,j;MGraph G;AdjType DMAXVEX;/*D(v)为 v0 到 v 的路径长度*/int pMAXVEXMAXVEX;/*p(v)记录 v0 到 v 的最短路径，若 pvw为 TRUE,则 w是从v0到v当前求得最短路径上的顶点*/G.vexnum=6;for(i=0;iG.vexnum;i+)/*G 数组初始化最大值*/G.arcs05=100; G.arcs12=5; G.arcs43=20; G.arcs45=60;for(j=0;jG.vexnum;j+)G.arcsij=INFINITY;G.arcs02=10;G.arcs04=30;G.arcs23=50;G.arcs35=10;/*以邻接矩阵形式输出图*/ShortestPath_DIJ(G,p,D);for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) printf(%12.0f,G.arcsij);printf(n);/*输出 V0 到其它各顶点的路径*/for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) printf(%3d,pij);printf(n);/*输出 V0 到其它各顶点的最短距离*/for(i=0;iG.vexnum;i+) printf(%.0f ,Di); final、D 和 p 数组的初始状态：-0 _32767 _ 000000 0 -03276700000010D =10P =101000下标=20327670000003030100010401001000015输出：32767 要换成 2147483648final =327673276710327673010032767327675327673276732767327673276732767503276732767327673276732767327673276710327673276732767203276760327673276732767327673276732767D 数组的变化情况下标初态i循环12345000000132767327673276732767327672101010101033276760505050430303030305100100906060V0入SV2入SV4入SV3入SV5入S不能到达VI丁_ 0 一132767110final =1D =50130160final、D 和 p 数组的终止状态：_ 000000 -000000101000P =100110100010100111下标=012345其中P中记录的是最短路径，D数组记录的是最短距离。即V0到各点的最短距离值为：0, 32767， 10， 50， 30， 60。4、Dijkstra 求最短路径的算法分析对于n个顶点的图，求一个顶点到其余顶点的最短路径，循环n-1次，加上修改最短路径的循环，是二层循环，故时间复杂度为O(n2)。若只求从源点到某一顶点间的最短路径, 和求到其余顶点间的最短路径相同，时间复杂度也是O(n2)。初值i=1i=2 000000 -000000101000p =000000100010100001i=3000000 -000000101000p =100110100010100111000000 -000000101000p =101100100010100001i=4000000 -000000101000p =100110100010100111000000 -000000101000p =100110100010100011i=5000000 -000000101000p =100110100010100111
展开阅读全文