《运筹》教学课件图论与网络第六章（三）最短路问题.ppt

《《运筹》教学课件图论与网络第六章（三）最短路问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§6.3最短路问题6.3.1最短路问题(theshortestpathproblem)最短路问题是重要的组合最优化问题之一,它不仅可以直接用于解决实际生产中的许多问题,如管道铺设、厂区布局、设备更新等问题，而且也常常作为解决其它组合优化问题的工具。6.3.2最短路问题的分类按照图是否有向进行分类：可以把最短路问题分为无向最短路问题和有向最短路问题。按照图的权进行分类：各边的权均为1的最短路问题（单位权最短路问题）、正权最短路问题、负权最短路问题。按照源点或始点个数进行分类：单源点最短路问题、多源点最短路问题及所有点间的最短路问题。6

2、.3.3课程所学的最短路问题无向、正权、单源点最短路问题无向、正权、所有点间最短路问题有向、正权、单源点最短路问题有向、正权、所有点间最短路问题6.3.4正权单源点最短路问题给定一个具有n个点、m条边的图G(V，E)，始点为s，边(x，y)的权w(x，y)为正实数。若点x为图中任意一点，设P是D中从s到x的一条路，定义路P的权是所有边的权之和，记为w(P)。单源点最短路问题就是在所有从s到x的路P中，求一条权最小的路P0满足w(P0)=min{w(P)}。表1：正权最短路问题历史进展情况来自：CombinatorialOptimiz

3、ation(VolumeA),page:103PolyhedraandEfficiency著6.3.5正权单源点最短路问题的历史续表1：正权最短路问题历史进展情况6.3.5正权单源点最短路问题的历史评价6.3.5正权单源点最短路问题的历史6.3.6单源点最短路问题的算法—Dijkstra算法6.3.6单源点最短路问题的算法—Dijkstra算法1234s一个例子6.3.6单源点最短路问题的算法—Dijkstra算法1234s一个例子6.3.6单源点最短路问题的算法—Dijkstra算法1234s一个例子6.3.7正权所有点间最短路问

4、题给定一个具有n个点、m条边的图G(V，E)，边(x，y)的权w(x，y)为正实数。若点x和点y为图中任意两点，则求任意两点x和y间的最短路径。6.3.7所有点间最短路问题Floyd—Warshall算法6.3.7所有点间最短路问题Floyd—Warshall算法6.3.7所有点间最短路问题Floyd—Warshall算法6.3.7所有点间最短路问题Floyd—Warshall算法6.3.7所有点间最短路问题Floyd—Warshall算法6.3.7所有点间最短路问题Floyd—Warshall算法Floyd-Warshall例子由

5、于在矩阵B(5)中b42=3，b43=4那么4到2的最短路径为4→3→2由于在矩阵B(5)中b52=3，b53=4,b54=5,那么5到2的最短路径为5→4→3→2Floyd-Warshall例子Floyd-Warshall例子Floyd-Warshall例子Floyd-Warshall例子Floyd-Warshall例子Floyd-Warshall例子由于在矩阵B(5)中b42=3，b43=4那么4到2的最短路径为4→3→2由于在矩阵B(5)中b52=3，b53=4,b54=5,那么5到2的最短路径为5→4→3→2