最短路与网络流课件.ppt

《最短路与网络流课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章图与网络分析最短路问题最短路的应用第一讲：最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型，如设备更新、管道的铺设、线路的安排、厂区的布局等。最短路问题的一般提法是：设为连通图，图中各边有权(表示，之间没有边）,为图中任意两点，求一条道路，使它是从到的所有路中总权最小的路。即：最小。最短路算法中1959年由（狄克斯特洛）提出的算法被公认为是目前最好的方法，我们称之为算法。下面通过例子来说明此法的基本思想。条件：所有的权数思路：逐步探寻。下求到的最短路：1）从出发，向走。首先，从到的距离为0，给标号（

2、0）。画第一个弧。（表明已标号，或已走出）从出发，只有两条路可走，其距离为2）①可能最短路为①给划成粗线。③划第二个弧。②给标号（4）。①②表明走出后走向的最短路目前看是，最优距离是4。现已考察完毕第二个圈内的路，或者说，已完成的标号。①②3）接着往下考察，有三条路可走：可选择的最短路为①给划成粗线。③划第3个弧。②给标号（6）。③①②4）接着往下考察，有四条路可走：可选择的最短路为①给划成粗线。③划第4个弧。②给标号（8）。①②③④5）接着往下考察，有四条路可走：可选择的最短路为①给划成粗线。③划第5个弧。②给标号（9）。①②③④⑤6）接

3、着往下考察，有四条路可走：可选择的最短路为①给划成粗线。③划第6个弧。②给标号（13）。①②③④⑤⑥7）接着往下考察，有四条路可走：可选择的最短路为①同时给划成粗线。②分别给标号（14）。最后，从逆寻粗线到，得最短路：长度为15。第二讲：最短路问题的两个应用最短路问题在图论应用中处于很重要的地位，下面举两个实际应用的例子。例12/P264设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要负购买费。试确定一个5年计划，使总支出最小若已知设备在各年的购买费，及不同机器役

4、龄时的残值与维修费，如表8-2所示.项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210表8-2解：把这个问题化为最短路问题。用点表示第i年初购进一台新设备，虚设一个点，表示第5年底。边表示第i年购进的设备一直使用到第j年初（即第j-1年底）。边上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买费、维修的全部费用（可由表8-2计算得到）。这样设备更新问题就变为：求从到的最短路问题.⑴①⑵给划成彩线。②⑶①②给划成彩线。⑷③给划成彩线。④⑸①②③④给划

5、成彩线。⑤①②③④⑤⑹给划成彩线。计算结果：最短路①②③④⑤最短路路长为49。即：在第一年、第三年初各购买一台新设备为最优决策。这时5年的总费用为49。例13(选址问题P265)已知某地区的交通网络如图8-37所示，其中点代表居民小区，边代表公路，为小区间公路距离，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？解求中心的问题。解决方法：先求出到其它各点的最短路长如再求即为所求。比如求⑴⑵给划成彩线。⑶给划成彩线。给标号20。⑷给划成彩线。给标号30。⑸分别给划成彩线。分别给标号33。⑹给划成彩线。给标号63。其它

6、计算结果见下表：小区号030506393456093300203363153063502002050254050633320030183363936350300486393451525184801548603040336315063表8.1由于最小，所以医院应建在，此时离医院最远的小区距离为48。三.Floyd（佛洛伊德）算法这里介绍得Floyd（1962年）可直接求出网络中任意两点间的最短路。令网络中的权矩阵为其中当其他算法基本步骤为：⑴输入权矩阵例14/P266⑵计算其中例如：中不带角标的元素表示从到的距离（直接有边），带角标的元素表示

7、借为中间点时的最短路长。中不带角标的元素表示从到的距离（直接有边），带角标的元素表示借为中间点时的最短路长。在放开的基础上，再放开注意到：在放开点的基础上，再放开考察最短路。注意到：说明所有点经过并没有缩短路程。只有一个新增元素表示任意两点间的最短路长及其路径。第二讲最大流问题最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流、供水系统中有水流，金融系统中有现金流，通信系统中有信息流，等等。一．有关概念：例：下图是输油管道网，为起点，为终点，，，，为中转站，边上的数字表示该管道的最大输油能力（也称容量），记为，问应

8、如何安排各管道输油量，才能使从到的总输油量最大？①分别称为发点、收点。其余的点称为中间点。②每一个边上都给定一个容量的网络称为容量网络，记的每一个边上都给定一个实际流量的网络称为