圖論讀書報告

最短路徑問題圖論是數(shù)學(xué)的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點代表事物，用連接兩點的線表示相應(yīng)兩個事物間具有這種關(guān)系。圖論起源于著名的哥尼斯堡七橋問題。在哥尼斯堡的普萊格爾河上有七座橋?qū)⒑又械膷u及島與河岸聯(lián)結(jié)起來。問題是要從這四塊陸地中任何一塊開始，通過每一座橋正好一次，再回到起點。然而無數(shù)次的嘗試都沒有成功。歐拉在1736年解決了這個問題，他用抽像分析法將這個問題化為第一個圖論問題：即把每一塊陸地用一個點來代替，將每一座橋用聯(lián)接相應(yīng)的兩個點的一條線來代替，從而相當(dāng)于得到一個“圖”。歐拉證明了這個問題沒有解，并且推廣了這個問題，給出了對于一個給定的圖可以某種方式走遍的判定法則。這就是后來的歐拉路徑和歐拉回路。這項工作使歐拉成為圖論〔及拓?fù)鋵W(xué)〕的創(chuàng)始人。最短路徑問題是圖論解決的典型實際問題之一，可用來解決廠區(qū)布局、管路鋪設(shè)、線路安裝等實際問題。在日常生活中，我們?nèi)绻枰３Ｍ礎(chǔ)地區(qū)和B地區(qū)之間，我們最希望知道的可能是從A地區(qū)到B地區(qū)間的眾多路徑中，那一條路徑的路途最短。最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由結(jié)點和路徑組成的）中兩結(jié)點之間的最短路徑。算法具體的形式包括：（1）確定起點的最短路徑問題：即已知起始結(jié)點，求最短路徑的問題。（2）確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題。（3）確定起點終點的最短路徑問題：即已知起點和終點，求兩結(jié)點之間的最短路徑。（4）全局最短路徑問題：求圖中所有的最短路徑。一、相關(guān)定義1.1圖一集元素及它們之間的某種關(guān)系稱為圖。具體地說，圖是一個二元組（V，E），其中集合V稱為頂點集，集合E是V中元素組成的某些無序?qū)Φ募希Q為邊集。例：給定G=(V,E)，其中這便定義出一個圖。1.2賦權(quán)圖對圖G的每條邊e，賦以一個實數(shù)w(e)，稱為邊e的權(quán)。每個邊都賦有權(quán)的圖稱為賦權(quán)圖。權(quán)在不同的問題中會有不同的含義。例如交通網(wǎng)絡(luò)中，權(quán)可能表示運費、里程或道路的造價等。1.3最短路徑問題給定賦權(quán)圖G及G中兩點u,v，求u到v的具有最小權(quán)的路（稱為u到v的最短路）。注：賦權(quán)圖中路的權(quán)也稱為路的長，最短(u，v)路的長也稱為u，v間的距離，記為d(u，v)。最短路徑問題是圖論中的一個基本問題。在賦權(quán)圖中，每條邊都有一個數(shù)值——權(quán)（代表其長度、成本、時間等），找出兩節(jié)點之間總權(quán)和最小的路徑就是最短路徑問題。最短路徑算法包括指定頂點對之間的最短路徑算法和所有頂點間的最短路徑算法，前者對于運輸?shù)暮侠砘哂兄匾碚撘饬x，而后者的意義在于選擇合理的中轉(zhuǎn)中心，使得總的費用最少。最短路問題是一個優(yōu)化問題，屬于網(wǎng)絡(luò)優(yōu)化和組合優(yōu)化的范疇。在圖論中最典型的兩種求最短路徑算法分別是Dijkstra算法和Floyd算法，其中Dijkstra算法適用于前者，而Floyd算法適用于后者。二、Dijkstra算法2.1

Dijkstra算法Dijkstra算法是典型最短路算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。2.2

Dijkstra算法思想Dijkstra算法思想為：設(shè)G=(V,E)是一個帶權(quán)有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑,就將加入到集合S中，直到全部頂點都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度。2.3

Dijkstra算法具體步驟以下面的例子說明如下圖，設(shè)A為源點，求A到其他各頂點（B、C、D、E、F）的最短路徑。線上所標(biāo)注為相鄰線段之間的距離，即權(quán)值。

算法執(zhí)行步驟如下表：步驟S集合中U集合中1選入A，此時S=<A>此時最短路徑A→A=0以A為中間點，從A開始找U=<B、C、D、E、F>A→B=6，A→C=3，A→其它U中的頂點=∞，發(fā)現(xiàn)A→C=3權(quán)值為最短2選入C，此時S=<A、C>此時最短路徑A→A=0，A→C=3以C為中間點，從A→C=3這條最短路徑開始找U=<B、D、E、F>A→C→B=5(比上面第一步的A→B=6要短)此時到D權(quán)值更改為A→C→B=5，A→C→D=6，A→C→E=7，A→C→其它U中的頂點=∞，發(fā)現(xiàn)A→C→B=5權(quán)值為最短3選入B，此時S=<A、C、B>此時最短路徑A→A=0，A→C=3，A→C→B=5以B為中間點從A→C→B=5這條最短路徑開始找U=<D、E、F>A→C→B→D=10(比上面第二步的A→C→D=6要長)此時到D權(quán)值更改為A→C→D=6，A→C→B→其它U中的頂點=∞，發(fā)現(xiàn)A→C→D=6權(quán)值為最短4選入D，此時S=<A、C、B、D>此時最短路徑A→A=0，A→C=3，A→C→B=5，A→C→D=6以D為中間點，從A→C→D=6這條最短路徑開始找U=<E、F>A→C→D→E=8(比上面第二步的A→C→E=7要長)此時到E權(quán)值更改為A→C→E=7，A→C→D→F=9發(fā)現(xiàn)A→C→E=7權(quán)值為最短5選入E，此時S=<A、C、B、D、E>此時最短路徑A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，以E為中間點，從A→C→E=7這條最短路徑開始找U=<F>A→C→E→F=12(比上面第四步的A→C→D→F=9要長)此時到F權(quán)值更改為A→C→D→F=9發(fā)現(xiàn)A→C→D→F=9權(quán)值為最短6選入F，此時S=<A、C、B、D、E、F>此時最短路徑A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，A→C→D→F=9U集合已空，查找完畢。三、Floyd算法3.1 Floyd算法的基本思想全部頂點間最短路徑算法具有代表性的是1962年由福勞德（Floyd）提出的算法。他的主要思想是從代表任意2個頂點vi到vj的距離的帶權(quán)鄰接矩陣開始，每次插入一個頂點vk，然后將vi到vj間的已知最短路徑與插入頂點vk作為中間頂點（一條路徑中除始點和終點外的其他頂點）時可能產(chǎn)生的vi到vj路徑距離比較，取較小值以得到新的距離矩陣，如此循環(huán)迭代下去，依次構(gòu)造出n個矩陣D(1)，D(2)，…，D(n)，當(dāng)所有的頂點均作為任意2個矩陣vi到vj中間頂點時得到的最后的帶權(quán)鄰接矩陣D(n)就反映了所有頂點對之間的最短距離信息，成為圖G的距離矩陣。最后對G中各行元素求和值并比較大小，決定單個或多個最佳的點。3.2Floyd算法構(gòu)造距離矩陣的原理對一個有n個頂點的圖G，將頂點用n個整數(shù)（從1到n）進行編號。把G的帶權(quán)鄰接矩陣W作為距離的初值，即D(0)=(dij(0))nxm=W。第一步構(gòu)造D(1)=(dij(1))nxm，其中dij(1)=min{dij(0)，di1(0)+d1j(0)}是從vi到vj的只允許以v1作為中間點的路徑中最短路長度。第二步構(gòu)造D(2)=(dij(2))nxm，其中dij(2)=min{dij(1)，di2(1)+d2j(1)}是從vi到vj的只允許以v1、v2作為中間點的路徑中最短路長度。第n步構(gòu)造D(n)=(dij(n))nxm，其中dij(n)=min{dij(n)，din(n)+dnj(n)}是從vi到vj的只允許以v1、v2、…、vn作為中間點的路徑中最短路長度，即是從vi到vj中間可插入任何頂點的路徑中最短路的長度，因此D(n)即是距離矩陣。3.3Floyd算法具體步驟以下面的例子說明某城市考慮在開發(fā)區(qū)建立垃圾中轉(zhuǎn)站。在垃圾站的選址問題中，點表示可供選址的垃圾站，而其間的連線表示運輸費用，其需求點之間運費如圖所示（英文字母為可選垃圾站點，數(shù)字為相鄰站點之間的運費）。在垃圾中轉(zhuǎn)站的選址中，要求該中轉(zhuǎn)站到其他站點的距離最短，即運輸費用最少，這里通過運用最短路徑Floyd算法可以求出該網(wǎng)點布局的最佳中轉(zhuǎn)站。abcde108433265首先，確定矩陣D(0)其中若頂點vi（編號i）到vj（編號j）有邊相連，則dij(0)abcde108433265然后，對k=1，2，3，…，n依次利用算法原理中第n步遞歸公式，由已知的Dn-1各元素確定Dn的各元素值。插入頂點a后D(1)的各元素和相應(yīng)的最短路徑因為對稱性，D(1)的第一行元素和第一列元素與D(0)相同，D(1)的主對角線上的元素均為0，所以只需計算其余6個元素的值：由此可知，依次插入b，c，d，e，可得不斷更新的距離矩陣：最終求得距離矩陣D(5)的各元素值就是相應(yīng)頂點間的最短路徑。最后，計算第i行各元素值之和C(vi)即為vi到其他各點的