1、Floyd算法Dijkstra算法两个例子的求解引例2：最廉价航费表的制定引例1：最短运输路线问题最短路径问题的0-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+113141023741165981
4、15运行上页程序输出：运行上页程序输出：dis=21path=1 8 9 10 11 因此顶点因此顶点1到顶点到顶点11的最短路径为的最短路径为18 9 10 11,其长度为其长度为21。16050402510500152025150102040201001025252010055102525550050402510500152025150102040201001025252010055102525550人有了知识，就会具备各种分析能力，人有了知识，就会具备各种分析能力，明辨是非的能力。明辨是非的能力。所以我们要勤恳读书，广泛阅读，所以我们要勤恳读书，广泛阅读，古人说古人说“书中自有黄金屋。书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，给我们巨大的精神力量，鼓舞我们前进鼓舞我们前进。
