1、Floyd算法Dijkstra算法两个例子的求解引例2：最廉价航费表的制定引例1：最短运输路线问题3102374116598140504025105001520251501020402010010252520100551025255505l定义：设定义：设P(u,v)是加权图是加权图G中从中从u到到v的路径的路径,则该路则该路径上的边权之和称为该路径的权径上的边权之和称为该路径的权,记为记为w(P). 从从u到到v的路径中权最小者的路径中权最小者 P*(u,v)称为称为u到到v的最短路径的最短路径.10237411659811023741165981算法步骤算法步骤S: 具有永久标号的顶点集具
2、有永久标号的顶点集;l(v): v的标记的标记; f(v):v的父顶点的父顶点,用以确定最短路径用以确定最短路径; 输入加权图的带权邻接矩阵输入加权图的带权邻接矩阵w=w(vi,vj)nxm.1)初始化初始化 令令l(v0)=0,S= ; v v0 ,l(v)= ;2)更新更新l(v), f(v) 寻找不在寻找不在S中的顶点中的顶点u,使使l(u)为最小为最小.把把u加入到加入到S中中,然后对所有不在然后对所有不在S中的顶点中的顶点v,如如l(v)l(u)+w(u,v),则则更新更新l(v),f(v), 即即 l(v)l(u)+w(u,v),f(v)u;3)重复步骤重复步骤2), 直到所有顶点
3、都在直到所有顶点都在S中为止中为止.91023741165981算法步骤算法步骤 d(i,j) : i到到j的距离的距离; path(i,j): i到到j的路径上的路径上i的后继点的后继点; 输入带权邻接矩阵输入带权邻接矩阵a(i,j).1）赋初值）赋初值 对所有对所有i,j, d(i,j)a(i,j) , path(i,j)j,k=l.2）更新）更新d(i,j) , path(i,j) 对所有对所有i,j, 若若d(i,k)+d(k,j)d(i,j),则则 d(i,j)d(i,k)+d(k,j) , path(i,j)path(i,k) , k k+13）重复）重复2)直到直到k=n+11314102374116598115运行上页程序输出：运行上页程序输出：dis = 21path = 1 8 9 10 11 因此顶点因此顶点1到顶点到顶点11的最短路径为的最短路径为18 9 10 11, 其长度为其长度为21。16050402510500152025150102040201001025252010055102525550050402510500152025150102040201001025252010055102525550
