最短路算法

最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型，如设备更新、管道的铺设、线路的安排、厂区的布局等。最短路问题的一般提法是：设为连通图，图中各边有权(表示，之间没有边）,为图中任意两点，求一条道路，使它是从到的所有路中总权最小的路。即：),(EVG),(jivvijlijliv,svjvtvsvtv),()(jivvijlL最小。3最短路问题最短路算法中1959年由（狄克斯特洛）提出的算法被公认为是目前最好的方法，我们称之为算法。下面通过例子来说明此法的基本思想。DijkstraDijkstra条件：所有的权数0ijl思路：逐步探寻。1v2v3v5v7v8v6v4v46761519554471v2v3v5v7v8v6v4v4676151955447下求到的最短路：1v8v1）从出发，向走。首先，从到的距离为0，给标号（0）。画第一个弧。（表明已标号，或已走出）1v8v1v1v1v1v1v)0(从出发，只有两条路可走，其距离为1v),,(21vv),(31vv2）,412l.613l①1v2v3v5v7v8v6v4v4676151955447)0(可能最短路为4}6,4min{},min{},min{13121312llkk),(21vv2v)4(①给划成粗线。③划第二个弧。②给标号（4）。①②1v2v3v5v7v8v6v4v4676151955447)0()4(表明走出后走向的最短路目前看是，最优距离是4。1v8v),(21vv现已考察完毕第二个圈内的路，或者说，已完成的标号。,1v2v①②1v2v3v5v7v8v6v4v4676151955447)0()4(3）接着往下考察，有三条路可走：),,(42vv),,(31vv).,(52vv可选择的最短路为6}44,54,6min{},,min{},,min{2512241213252413dldllkkk),(31vv3v)6(①给划成粗线。③划第3个弧。②给标号（6）。③①②1v2v3v5v7v8v6v4676151955447)0()4()6(4）接着往下考察，有四条路可走：),,(42vv).,(52vv可选择的最短路为8}13,10,8,9min{},,,min{35342524kkkk5v4v),,(43vv).,(53vv),(52vv)8(①给划成粗线。③划第4个弧。②给标号（8）。①②③④1v2v3v5v7v8v6v4676151955447)0()4()6(5）接着往下考察，有四条路可走：),,(42vv可选择的最短路为9}14,13,10,9min{},,,min{57563424kkkk4v),,(43vv),,(65vv),(42vv)8().,(75vv4v)9(①给划成粗线。③划第5个弧。②给标号（9）。①②③④⑤1v2v3v5v7v8v6v4676151955447)0()4()6(6）接着往下考察，有四条路可走：),,(64vv可选择的最短路为13}14,13,16,18min{},,,min{57564746kkkk6v),,(74vv),,(65vv),(65vv)8().,(75vv4v)9()13(①给划成粗线。③划第6个弧。②给标号（13）。①②③④⑤⑥1v2v3v5v7v8v6v4676151955447)0()4()6(7）接着往下考察，有四条路可走：可选择的最短路为14}14,18,14,16min{},,,min{68675747kkkk),,(76vv),,(75vv)8(),,(75vv4v)9()13().,(86vv)14(),,(74vv)14(①同时给划成粗线。②分别给标号（14）。最后，从逆寻粗线到，得最短路：1v2v3v5v7v8v6v4676151955447)0()4()6()8(4v)9()13()14()14(8v1v86521vvvvv长度为14。最短路问题的两个应用最短路问题在图论应用中处于很重要的地位，下面举两个实际应用的例子。若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表所示.例1设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使用旧的还是购买新的？如果继续使用旧的，要付维修费；若要购买一套新的，要付购买费。试确定一个5年计划，使总支出最小.项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210解：把这个问题化为最短路问题。用点表示第i年初购进一台新设备，虚设一个点，表示第5年底。6viv边表示第i年购进的设备一直使用到第j年初（即第j-1年底）。边上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买费、维修的全部费用（可由表8-2计算得到）。),(jivv1v2v3v4v5v6v131219284059151520294122213014这样设备更新问题就变为：求从到的最短路问题.1v6v)12(2v3v4v5v6v131219284059151520294122213014⑴1v)0(①⑵12}59,40,28,19,,12min{},,,,min{1615141312kkkkk1v)0(),(21vv给划成彩线。②19}4112,2912,2012,1312,59,40,28,19min{},,,,,,,min{2625242316151413kkkkkkkk⑶)12(2v)19(3v)28(4v5v6v131219284059151520294122213014①1v)0(②),(31vv给划成彩线。28}49,40,33,53,41,32,59,40,28min{},,,,,,,,min{363534262524161514kkkkkkkkk⑷③),(41vv给划成彩线。④40}50,43,49,35,43,41,59,40min{},,,,,,,min{4645363526251615kkkkkkkk⑸)12(2v)19(3v)28(4v)40(5v6v131219284059151520294122213014①1v)0(②③④),(51vv给划成彩线。⑤)12(2v)19(3v)28(4v)40(5v6v131219284059151520294122213014①1v)0(②③④⑤49}55,50,49,53,59min{},,,,min{5646362616kkkkk⑹),(63vv给划成彩线。计算结果：最短路631vvv)12(2v)19(3v)28(4v)40(5v6v1319284059151520294122213014①1v)0(②③④⑤12最短路路长为49。即：在第一年、第三年初各购买一台新设备为最优决策。这时5年的总费用为49。例2(选址问题P)已知某地区的交通网络如图8-37所示，其中点代表居民小区，边代表公路，为小区间公路距离，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？1v6v3v2v4v5v7v301520301520256018解求中心的问题。解决方法：先求出到其它各点的最短路长如ivjd},,max{)(7211dddvD再求)}(,),(),(min{721vDvDvD即为所求。1v)18(6v2v7v30152030152025185v60)0(4v比如求)(4vD⑴4v)0(⑵18}18,30,20min{},,min{464543kkk),(64vv给划线。3v1v)18(6v2v7v30152030152025185v60)0(4v)20(3v20}33,33,43,30,20min{},,,,min{6762634543kkkkk⑶),(34vv给划线。给标号20。3v1v)18(6v)33(2v7v3015203015202518)30(5v60)0(4v)20(3v30}33,33,40,80,30min{},,,,min{6762323545kkkkk⑷),(54vv给划线。给标号30。5v1v)18(6v)33(2v3015203015202518)30(5v60)0(4v)20(3v33}33,33,40min{},,min{676232kkk⑸),,(26vv分别给划线。分别给标号33。72,vv)33(7v),(76vv)60(1v)18(6v1v3015203015202518)30(5v60)0(4v)20(3v63}63min{}min{21k⑹给划成彩线。给标号63。),(12vv)33(7v)33(2v其它计算结果见下表：小区号0305063934560933002033631530635020020502540506333200301833639363503004863934515251848015486030403363150631v1v3v3v2v2v4v4v5v5v6v6v7v7v)(ivD由于最小，所以医院应建在，此时离医院最远的小区距离为48。48)(6vD6v5vFloyd（佛洛伊德）算法这里介绍得Floyd（1962年）可直接求出网络中任意两点间的最短路。令网络中的权矩阵为,)(nnijdD其中ijijld当其他Evvji),(算法基本步骤为：⑴输入权矩阵.)0(DD1v2v2105v3v4vDD)0(例252231644804424062820322100521501v1v2v3v4v5v3v2v4v5v⑵计算nnkijkdD)()()(nk,,2,1其中},min{)1()1()1()(kkjkikkijkijdddd例如：6}15,10{},min{)0(13)0(21)0(23)1(23dddd)1(D044240372820322760521504134122142131v1v2v3v4v5v3v2v4v5v},min{)0(1)0(1)0()1(jiijijdddd中不带角标的元素表示从到的距离（直接有边），带角标的元素表示借为中间点时的最短路长。ivjv1v)1(D)0(D04424062820322100521501v1v2v3v4v5v3v2v4v5vikjkjikddd)2(D},min{)1(2)1(2)1()2(jiijijdddd2v,1v1v1v2v3v4v5v3v2v4v5v0442740372520322760572150521413412325214213125中不带角标的元素表示从到的距离（直接有边），带角标的元素表示借为中间点时的最短路长。ivjv)2(D)1(D044240372820322760521504134122142131v1v2v3v4v5v3v2v4v5v在放开的基础上，再放开1v2v)3(D1v1v2v3v4v5v3v2v4v5v044264036252032276056214053141341323252142131325132},min{)2(3)2(3)2()3(jiijijdddd)2(D1v1v2v3v4v5v3v2v4v5v0442740372520322760572150521413412325214213125注意到：},min{)2(35)2(13)2(15)3(15dddd1325325136}51,7min{在放开点的基础上，再放开考察最短路。,1v2v3v)3(D1v1v2v3v4v5v3v2v4v5v04426403625203227605621