matlab最短路径算法.ppt

最短路径问题最短路径问题最短路径问题主要内容主要内容Dijkstra算法例子的求解例:最短运输路线问题3如图的交通网络,每条弧上的数字代表车辆在该路段行如图的交通网络,每条弧上的数字代表车辆在该路段行驶所需的时间,有向边表示单行道,无向边表示可双向驶所需的时间,有向边表示单行道,无向边表示可双向行驶。若有一批货物要从行驶。若有一批货物要从11号顶点运往号顶点运往1111号顶点,问运号顶点,问运货车应沿哪条线路行驶,才能最快地到达目的地?货车应沿哪条线路行驶,才能最快地到达目的地?例:例:最短运输路线问题最短运输路线问题1023741165981335512122210106611558888779999332222774最短路径问题最短路径问题?定义:设P(u,v)是加权图G中从u到v的路径,则该路径上的边权之和称为该路径的权,记为w(P). 从u到v的路径中权最小者 P*(u,v)::1)1)寻求从一固定顶点到其余各点的最短路径寻求从一固定顶点到其余各点的最短路径;;2)2)有向图、无向图和混合图有向图、无向图和混合图;;3)3)权非负权非负..算法思路:算法思路:采用标号作业法采用标号作业法,,每次迭代产生一个永久标号每次迭代产生一个永久标号, , 从而生长一颗以从而生长一颗以vv00为根的最短路树为根的最短路树,,在这颗树上每个在这颗树上每个顶点与根节点之间的路径皆为最短路径顶点与根节点之间的路径皆为最短路径..102374116598133551122221100661155888877999933222277DijkstraDijkstra算法算法————算法步骤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),然后对所有不在S中的顶点v,如l(v)>l(u)+w(u,v),则更新l(v),f(v), 即 l(v)?l(u)+w(u,v),f(v)?u;?重复步骤2), (程序(DijkstraDijkstra算法)算法)function [min,path]=dijkstra(w,start,terminal)function [min,path]=dijkstra(w,start,terminal)n=size(w,1); label(start)=0; f(start)=start;n=size(w,1); label(start)=0; f(start)=start;for i=1:nfor i=1:n if i~=start if i~=start label(i)=inf; label(i)=inf;end, endend, ends(1)=start; u=start;s(1)=start; u