最短路问题

null 6-2. 最 短 路 问 题 6-2. 最 短 路 问 题 null 某单行线交通网如下图所示，每弧旁的数字示通过这条单行线所需要的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。 引例一、问题的提法及应用背景一、问题的提法及应用背景问题的提法应用背景寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数为最小的通路。管道铺设、线路安排、厂区布局、物流中心的选址等。二、最短路算法二、最短路算法三、Dijkstra算法三、Dijkstra算法 狄克斯特拉 （Dijkstra） 算法又称“D氏标号法” 2、求解思路——从始点出发，逐步顺序地向 外探寻，每向外延伸一步都 要求是最短的。 1、使用条件——网络中所有的弧权均 非负，即 。三、Dijkstra算法三、Dijkstra算法nullnull用Dijkstra算法求解下列网络图的最短路问题。用Dijkstra算法求解下列网络图的最短路问题。解：先将图5-1的网络用矩阵形式表示出来:解：先将图5-1的网络用矩阵形式表示出来:nullv1{v2，…，v7}v1 v2 v3 v4 v5 v6 v7 0 - - - - - - 0+20+5 2 5 - - - - v2v3v4v5v6{v3，…，v7}{v4，…，v7}{v5，v6，v7}{v5，v7}2+22+42+6 4 6 8 - -4+14+3 5 8 7 - 5+45+15+4 8 6 96+2 8 8{v7}8+18null反向追踪，得到最优路线：4v1v2v3v4v6v5v722561413412nullv6v7{v5，v7}{v5}v1 v2 v3 v4 v5 v6 v7 6+2 8 8 8+18 8 6 9反向追踪，得到相同的最优路线。 在得到从起点到终点的最短路长的同时，还能得到什麽附加信息 ？nullD氏标号法（Dijkstra）的特点（获得的附加信息）：四、Dijkstra算法及应用拓展四、Dijkstra算法总结及应用拓展…网络中所有的弧权均非负适用 条件…从始点出发，逐步顺序地向外探寻， 每向外延伸一步都要求是最短的。 求解思路…能得到从 起点到各点的最短路线和 最短路长。特点作业作业 1、 用Dijkstra方法求解下列各图中从v1到v7的最短路。 作业作业2、