dijkstra 算法求最短路径分析.docVIP

路径优化数学模型 Dijkstra原理： Dijkstra算法概述：Dijkstra算法是由E.w.Dijkstra于1959年提出的一个适用于所有弧的权为非负的最短路径算法。它可给出从某固定结点到图中其它所有结点的最短距离，时间复杂度为n2，其中n为结点个数。 Dijkstra算法描述：首先引进辅助变量dist【】，它的每一个分量dist【i】表示已经找到的从开始点V0到每一个终点Vi的最短路径。它的初态为：如果V0到Vi有弧，则dist【i】为弧的权值，如无弧 ，则dist【i】为无穷大。其中，长度为dist【j】=Min{dist【i】vi属于V}的路径是从V0出发的长度最短的一条最短路径，此路径为（v0，vj）。 当按长度递增的顺序来产生各个最短路径的时候，设S为已经求得的最短路径的顶点集合。可以证明：下一条最短路径或者是弧（v0，vx），或者是中间经过S中的某些顶点，而后到达的vx的路径。 通过反证法，可以得到，下一条最短路径上，不可能有不在S中的结点。 一般情况下，下一条最短路径dist【j】=min{dist【i】vi属于V-S}i。其中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）上的权值。dist【i】=garcs【v0】【vi】； 将v0到其余结点的路径长度初始化为权值。 （2）选择vk，使得dist【vk】=min{dist【i】vi属于V-S} Vk为目前求得的下一条从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]=dijkstra[w,start,terminal]; n=size(w,1); label(start)=0; f(start)=start; for i=1:n; if i~=start label(i)=inf; end,end s(1)=start; u=start; while length(s)n for i=1:n; ins=0; for j=length(s) if i==j; ins=1; end,end if ins==0; v=i; if label(v)(label(u)+w(u,v)); label= label(u)+w(u,v); f(v)=u; end,end,end v1=0; k=inf; for i=1:n; ins=0; for j=length(s) if i==j; ins=1; end,end if ins==0; v=i; if klabel(v); k=label(v); v1=v; end,end,end s(length(s)+1)=v1; u=v1; end; min=label(terminal); path(1)=terminal; i=1; while path(i)~=start path(i+1)=f(path(i)); i=i+1; end path(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,vj)]nxm. 初始化 令l(v0)=0,S=(;( v(v0 ,l(v)=(; 更新l(v), f(v) 寻找不在S中的顶点u,使l(u)为最小.把u加入到S中,然后对所有不在S中的顶点v,如l(v)l(u)+w