迪杰斯特拉算法

迪杰斯特拉算法实现第九组11123529-罗凯耀11123575-王鸣迪杰斯特拉--算法思想按从某顶点到其它顶点的路径长度递增的方式,逐渐求到各顶点的最短路径。设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs}。当求得第一条最短路径(Vs，Vi)后，S为{Vs，Vi}。根据以下结论可求下一条最短路径。设下一条最短路径终点为Vj，则Vj只有：◆源点到终点有直接的弧Vs，Vj；◆从Vs出发到Vj的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj。若定义一个数组dist[n]，其每个dist[i]分量保存从Vs出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：dist[i]=Min{dist[k]|Vk∈V-S}利用上述公式就可以依次找出下一条最短路径。迪杰斯特拉-算法思想源迪杰斯特拉算法--数据组织源有n个结点的网络•数据源•已确定结点集S•待选结点集V-S•结点临时最短路径长度•结点临时最短路径迪杰斯特拉算法—步骤①令S={Vs}，用带权的邻接矩阵表示有向图，对图中每个顶点Vi按以下原则置初值：②选择一个顶点Vj，使得：Distance[j]=Min{Distance[k]|Vk∈V-S}Vj就是求得的下一条最短路径终点，将Vj并入到S中，即S=S∪{Vj}。③对V-S中的每个顶点Vk，修改dist[k]，方法是：若Distance[j]+WjkDistance[k]，则修改为：Distance[k]=Distance[j]+Wjk(Vk∈V-S)④重复②，③，直到S=V为止。Wsii≠s且vs,vi∈E，wsi为弧上的权值∞i≠s且vs,vi不属于Edist[i]=0i=s迪杰斯特拉算法—实现•voidDijkstra(MGraphg,intstart,intend)•{•intdist[MAXV],path[MAXV];•ints[MAXV];•intmindis,i,j,u;•for(i=0;ig.n;i++)•{•dist[i]=g.edges[start][i];//dist数组初始化•s[i]=0;•if(g.edges[start][i]INF)•path[i]=start;•else•path[i]=-1;//path数组初始化•}•s[start]=1;//顶点start加入顶点集合s•path[start]=0;•for(i=0;ig.n;i++)//选择不在集合s中且具有最短路径的顶点•{•mindis=INF;•for(j=0;jg.n;j++)•{•if(s[j]==0&&dist[j]mindis)•{•u=j;•mindis=dist[j];•}•}•s[u]=1;//将顶点u加入集合•for(j=0;jg.n;j++)//修改dist和path•{•if(s[j]==0)•{•if((g.edges[u][j]INF)&&(dist[u]+g.edges[u][j]dist[j]))•{•dist[j]=dist[u]+g.edges[u][j];•path[j]=u;•}•}•}•}•Dispath(g,dist,path,s,g.n,start,end);•}已完成结点集S,本次最近点ABCDEF1{}DistancePath2DistancePath3DistancePath4DistancePath5(n-1)DistancePathEFDBCA82530181071540181004070158023050BACDEFBACDEF运算过程表邻接矩阵图•数据源——邻接矩阵•已确定结点集S•待选结点集V-S•结点临时最短路径长度——Distance数组•结点临时最短路径——Path数组Dijkstra算法--数据组织已完成结点集，本次最近点ABCDEF1{A,},CDistance0530PathA-1AA-1-12DistancePath3DistancePath4DistancePath5(n-1)DistancePath运算过程表Dijkstra算法—例子EFDBCA82530181071540181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径已完成结点集，本次最近点ABCDEF1{A,},CDistance0530PathA-1AA-1-12{A,C},FDistance02053012PathACAA-1C3DistancePath4DistancePath5(n-1)DistancePath运算过程表Dijkstra算法—例子EFDBCA82530181071540181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径已完成结点集，本次最近点ABCDEF1{A,},CDistance0530PathA-1AA-1-12{A,C},FDistance02053012PathACAA-1C3{A,C,F},BDistance0205223012PathACAFFC4DistancePath5(n-1)DistancePath运算过程表Dijkstra算法—例子EFDBCA82530181071540181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径已完成结点集，本次最近点ABCDEF1{A,},CDistance0530PathA-1AA-1-12{A,C},FDistance02053012PathACAA-1C3{A,C,F},BDistance0205223012PathACAFFC4{A,C,F,B},DDistance0205222812PathACAFBC5(n-1)DistancePath运算过程表Dijkstra算法—例子EFDBCA82530181071540181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径已完成结点集，本次最近点ABCDEF1{A,},CDistance0530PathA-1AA-1-12{A,C},FDistance02053012PathACAA-1C3{A,C,F},BDistance0205223012PathACAFFC4{A,C,F,B},DDistance0205222812PathACAFBC5(n-1){A,C,F,B,D},EDistance0205222812PathACAFBC运算过程表Dijkstra算法—例子EFDBCA82530181071540181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径最短路径结点集ABCDEF{A,C,F,B,D,E}Distance0205222812PathACAFBC运算结果Dijkstra算法—例子0181004070158023050BACDEFBACDEF邻接矩阵图EFDBCA8510715•通过Distance数组得到最短路径长度：D:22•通过对Path数组的反向搜索得到最短路径，如D结点相对于源点A的最短路径：DFCA例：计算从A点出发的单源最短路径Dijkstra算法的主要执行是：◆数组变量的初始化：时间复杂度是O(n)；◆求最短路径的二重循环：时间复杂度是O(n2)；因此，整个算法的时间复杂度是O(n2)。Dijkstra算法—算法分析