dijkstra 算法求最短路径分析

1、路径优化数学模型Dijkstra原理：1.1 1.2 Dijkstra算法描述：首先引进辅助变量dist【】，它的每一个分量dist【i】表示已经找到的从开始点V0到每一个终点Vi的最短路径。它的初态为：如果V0到Vi有弧，则dist【i】为弧的权值，如无弧 ，则dist【i】为无穷大。其中，长度为dist【j】=Mindist【i】vi属于V的路径是从V0出发的长度最短的一条最短路径，此路径为（v0，vj）。当按长度递增的顺序来产生各个最短路径的时候，设S为已经求得的最短路径的顶点集合。可以证明：下一条最短路径或者是弧（v0，vx），或者是中间经过S中的某些顶点，而后到达的vx的路径。通过反

2、证法，可以得到，下一条最短路径上，不可能有不在S中的结点。一般情况下，下一条最短路径dist【j】=mindist【i】vi属于V-Si。其中dist【i】的权值或者是（v0，vi）的权值，或者是dist【k】（Vk属于V-S）和弧（vk，vi）上的权值之和。可以将图中的顶点分为分为两座；S以求出的最短路径的终点集合（开始为v0）；V-S尚未求出最短路径的顶点集合（开始为V-v0的全部结点）；按最短路径长度递增的顺序将第二组结点加入到第一组中。1.3 Dijkstra实现Dijkatra算法的一般步骤如下：（1）g为用邻接矩阵表示的带权图，则garcs【i】【j】表示弧（vi，vj）上的权值。

3、dist【i】=garcs【v0】【vi】；将v0到其余结点的路径长度初始化为权值。（2）选择vk，使得dist【vk】=mindist【i】vi属于V-SVk为目前求得的下一条从v0出发的最短路径的终点；（3）修改从v0出发到集合V-S上任意顶点vi的最短路径长度，如果，dist【k】+garcs【k】【i】dist【i】，那么dist【i】= dist【k】+garcs【k】【i】。（4）重复（2）（3）共n-1次，即可按最短路径长度的递增顺序，逐个求出V0到其它每个顶点的最短路径长度。1.3 代码Function min,path=dijkstraw,start,terminal;n=s

4、ize(w,1;label(start=0;f(start=start;for i=1:n;if i=startlabel(i=inf;end,ends(1=start;u=start;while length(s for i=1:n;ins=0;for j=length(sif i=j;ins=1;end,endif ins=0;v=i;if label(v>(label(u+w(u,v;label= label(u+w(u,v;f(v=u;end,end,endv1=0;k=inf;for i=1:n;ins=0;for j=length(sif i=j;ins=1;end,endi

5、f ins=0;v=i;if k>label(v;k=label(v;v1=v;end,end,ends(length(s+1=v1;u=v1;end;min=label(terminal;path(1=terminal;i=1;while path(i=startpath(i+1=f(path(i;i=i+1;endpath(i=start;L=length(path;path=path(L:-1:1;调用格式为min,path=dijkstra(w,start,terminal其中输入变量w为所求图的带权邻接矩阵，start, terminal分别为路径的起点和终点的号码。返回start到terminal的最短路径path及其长度min.注意：顶点的编号从1开始连续编号。S: 具有永久标号的顶点集;l(v: v的标记; f(v:v的父顶点,用以确定最短路径;输入加权图的带权邻接矩阵w=w(vi,vjnxm.1 初始化 令l(v0=0,S=; vv0 ,l(v=;2 更新l(v, f(v寻找不在S中的顶点u,使l(u为最小.把u加入到S