迪杰斯特拉算法

迪杰斯特拉算法实现第九组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]+Wjk<Distance[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;i<g.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;i<g.n;i++)//选择不在集合s中且具有最短路径的顶点{mindis=INF;for(j=0;j<g.n;j++){if(s[j]==0&&dist[j]<mindis){u=j;mindis=dist[j];}}s[u]=1;//将顶点u参加集合for(j=0;j<g.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);}EFDBCA8253018107154úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF运算过程表邻接矩阵图数据源——邻接矩阵已确定结点集S待选结点集V-S结点临时最短路径长度——Distance数组结点临时最短路径——Path数组Dijkstra算法--数据组织运算过程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径运算过程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径运算过程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径运算过程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径运算过程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径运算结果Dijkstra算法—例子úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF邻接矩阵图EFDBCA8510715通过Distance数组得到最短路径长度：D: