迪杰斯特拉算法

迪杰斯特拉算法实现第九组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);}已完成结点集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算法—例子úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDE