圖論的基本算法

圖論基本算法長(zhǎng)沙市雅禮中學(xué)朱全民圖圖的概念

G=(V,E)圖的基本概念有向圖、頂點(diǎn)、入度、出度、弧、環(huán)無(wú)向圖、邊、路徑、頂點(diǎn)的度、鄰接簡(jiǎn)單圖、完全圖平面圖、二分圖過(guò)河一擺渡人欲將一只狼,一頭羊,一籃菜從河西渡過(guò)河到河?xùn)|.由于船小,一次只能帶一物過(guò)河，并且狼與羊,羊與菜不能獨(dú)處.給出渡河方法.

解：用四維0-1向量表示(人,狼,羊,菜)在河西岸的狀態(tài)(在河西岸則分量取1,否則取0),共有24=16種狀態(tài).在河?xùn)|岸的狀態(tài)類(lèi)似記作.

由題設(shè),狀態(tài)(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允許的,從而對(duì)應(yīng)狀態(tài)(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允許的.

以可允許的10個(gè)狀態(tài)向量作為頂點(diǎn),將可能互相轉(zhuǎn)移的狀態(tài)用線段連接起來(lái)構(gòu)成一個(gè)圖.

根據(jù)此圖便可找到渡河方法.(1,1,1,1)

(1,1,1,0)

(1,1,0,1)

(1,0,1,1)

(1,0,1,0)(0,0,0,0)

(0,0,0,1)

(0,0,1,0)

(0,1,0,0)

(0,1,0,1)(0,1,0,1)

(0,1,0,0)

(0,0,1,0)

(0,0,0,1)

(0,0,0,0)(1,0,1,0)

(1,0,1,1)

(1,1,0,1)

(1,1,1,0)

(1,1,1,1)河西=(人,狼,羊,菜)河?xùn)|=(人,狼,羊,菜)將10個(gè)頂點(diǎn)分別記為A1,A2,…,A10,則渡河問(wèn)題化為在該圖中求一條從A1到A10的路.從圖中易得到兩條路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.圖的矩陣表示

權(quán)矩陣

無(wú)向圖G的權(quán)矩陣A是一個(gè)對(duì)稱(chēng)矩陣.

關(guān)聯(lián)矩陣若vi是ej的始點(diǎn);若vi是ej的終點(diǎn);若vi與ej不關(guān)聯(lián).

有向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有一個(gè)1,有且僅有一個(gè)

-

1.鄰接表表節(jié)點(diǎn)

typearcptr=^arcnode;arcnode=recordadjvex:vtxptr;nextarc:arcptr;info:…{和弧有關(guān)的其他信息}end;vex=Recordvexdata:…{和頂點(diǎn)有關(guān)的其他信息}firstarc:arcptr;end;adjlist=array[vtxptr]ofvexnode;鄰接表123456234^135^136^236^345^12456^拓?fù)渑判?/p>

按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。由此所得頂點(diǎn)的線性序列稱(chēng)之為拓?fù)溆行蛐蛄欣纾簩?duì)于有向圖BDAC可求得拓?fù)溆行蛐蛄校?/p>

ABCD或ACBDBDAC對(duì)于下列有向圖不能求得它的拓?fù)溆行蛐蛄小Ｒ驗(yàn)閳D中存在一個(gè)回路

{B,C,D}FUNCtoporder(vardig:adjlisttp):boolean;init(top2);m:=0;ve[1..n]:=0whileNotempty(top1)do[j:=pop(top1);push(top2,j);m:=m+1;k:=firstadj(dig,j);whilek<>0do[入度(k):=入度(k)-1;if入度(k)=0thenpush(top1,k);ifve[j]+dut(<j,k>)>ve[k]thenve[k]:=ve[j]+dut(<j,k>);k:=nextadj(dig,j,k)]]ifm<nthenreturn(false)elsereturn(true);endF;求拓?fù)湫蛄型負(fù)渑判蚝诵膯?wèn)題：給一些序關(guān)系，排出全序！一個(gè)一個(gè)排先排最大然后第二大…具體實(shí)現(xiàn)？每次取0出度點(diǎn)枚舉所有點(diǎn)嗎？0出度只可能是1出度變來(lái)的！O(n+m)神經(jīng)網(wǎng)絡(luò)

在蘭蘭的模型中，神經(jīng)網(wǎng)絡(luò)就是一張有向圖，圖中的節(jié)點(diǎn)稱(chēng)為神經(jīng)元，而且兩個(gè)神經(jīng)元之間至多有一條邊相連，下圖是一個(gè)神經(jīng)元的例子：

圖中，X1—X3是信息輸入渠道，Y1－Y2是信息輸出渠道，C1表示神經(jīng)元目前的狀態(tài)，Ui是閾值，可視為神經(jīng)元的一個(gè)內(nèi)在參數(shù)。神經(jīng)元按一定的順序排列，構(gòu)成整個(gè)神經(jīng)網(wǎng)絡(luò)。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無(wú)分為幾層；稱(chēng)為輸入層、輸出層，和若干個(gè)中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出信息，只從上一層神經(jīng)元接受信息。

神經(jīng)網(wǎng)絡(luò)蘭蘭規(guī)定，Ci服從公式：（其中n是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目）

公式中的Wji（可能為負(fù)值）表示連接j號(hào)神經(jīng)元和i號(hào)神經(jīng)元的邊的權(quán)值。當(dāng)Ci大于0時(shí)，該神經(jīng)元處于興奮狀態(tài)，否則就處于平靜狀態(tài)。當(dāng)神經(jīng)元處于興奮狀態(tài)時(shí)，下一秒它會(huì)向其他神經(jīng)元傳送信號(hào)，信號(hào)的強(qiáng)度為Ci。如此．在輸入層神經(jīng)元被激發(fā)之后，整個(gè)網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿?dòng)下進(jìn)行運(yùn)作?，F(xiàn)在，給定一個(gè)神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的狀態(tài)（Ci），要求你的程序運(yùn)算出最后網(wǎng)絡(luò)輸出層的狀態(tài)。

【輸入格式】

第一行是兩個(gè)整數(shù)n（1≤n≤20）和p。接下來(lái)n行，每行兩個(gè)整數(shù)，第i＋1行是神經(jīng)元i最初狀態(tài)和其閾值（Ui），非輸入層的神經(jīng)元開(kāi)始時(shí)狀態(tài)必然為0。再下面P行，每行由兩個(gè)整數(shù)i，j及一個(gè)整數(shù)Wij，表示連接神經(jīng)元i、j的邊權(quán)值為Wij?！据敵龈袷健?/p>

輸出包含若干行，每行有兩個(gè)整數(shù)，分別對(duì)應(yīng)一個(gè)神經(jīng)元的編號(hào)，及其最后的狀態(tài)，兩個(gè)整數(shù)間以空格分隔。僅輸出最后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號(hào)由小到大順序輸出！若輸出層的神經(jīng)元最后狀態(tài)均為0，則輸出NULL。分析

理解問(wèn)題的第一步就是認(rèn)真“讀題”。那么我們先來(lái)看一看這個(gè)題目涉及的問(wèn)題。研究一下題目中所給的圖的一些性質(zhì)，可以發(fā)現(xiàn)如下特點(diǎn)：1．圖中所有的節(jié)點(diǎn)都有一個(gè)確定的等級(jí)，我們記作Level(i)2．圖中所有的邊都是有向的，并且從Level值為i-1的節(jié)點(diǎn)指向Level值為i的節(jié)點(diǎn)我們不妨將其抽象為“階段圖”。更一般地，我們可以發(fā)現(xiàn)所有的階段圖都是有向無(wú)環(huán)的，這樣我們可以通過(guò)拓?fù)渑判騺?lái)得到期望的處理節(jié)點(diǎn)的順序。可行算法

由于階段圖的性質(zhì)使得該圖的所有邊所連接節(jié)點(diǎn)的等級(jí)都是相鄰的，因此就可以設(shè)計(jì)出一個(gè)基于寬度優(yōu)先搜索的算法：1．初始時(shí)將所有輸入層的節(jié)點(diǎn)放入隊(duì)列；2．取出隊(duì)列中的一個(gè)元素，不重復(fù)地?cái)U(kuò)展并處理該節(jié)點(diǎn)所發(fā)出的邊的目標(biāo)節(jié)點(diǎn)；3．如果隊(duì)列非空，則轉(zhuǎn)向2；4．輸出輸出層中所有滿(mǎn)足條件的節(jié)點(diǎn)。但是由于本題在問(wèn)題描述中并沒(méi)有明確的給出判斷一個(gè)節(jié)點(diǎn)是否是輸入節(jié)點(diǎn)，因此需要在算法進(jìn)行的過(guò)程當(dāng)中額外地考慮一些邊界情況的數(shù)據(jù)（這個(gè)過(guò)程即便是真實(shí)數(shù)據(jù)沒(méi)有這樣出也是要有的），下面給出的更一般的算法可能會(huì)更好的跳過(guò)這些邊界情況。1．對(duì)原圖中所有的節(jié)點(diǎn)進(jìn)行一次拓?fù)渑判颍?．按照拓?fù)漤樞蛱幚砻恳粋€(gè)節(jié)點(diǎn)；3．輸出輸出層中所有滿(mǎn)足條件的節(jié)點(diǎn)。歐拉道路和回路經(jīng)過(guò)每條邊一次且僅一次先看回路必要條件：所有點(diǎn)度為偶數(shù)充分條件：還是“所有點(diǎn)度為偶數(shù)”證明！把歐拉回路構(gòu)造出來(lái)“圈套圈”可能套不出來(lái)嗎？想一想歐拉道路和回路有向的情形入度=出度如何套圈？道路有兩個(gè)奇度點(diǎn)正好是起點(diǎn)和終點(diǎn)哪個(gè)是起點(diǎn)，哪個(gè)是終點(diǎn)？有向+無(wú)向怎么辦？網(wǎng)絡(luò)流！不要求掌握幼兒園的粉刷幼兒園里有很多房屋房屋與房屋之間連以走廊走廊與房屋之間有一扇門(mén)幼兒園長(zhǎng)想把門(mén)漆成綠色或者黃色，使得任意一條走廊兩頭門(mén)的顏色不同任意一間房屋上的門(mén)，綠色門(mén)的數(shù)量與黃色門(mén)的數(shù)量相差不超過(guò)1。如何實(shí)現(xiàn)？每個(gè)房屋的門(mén)都是偶數(shù)個(gè)…把奇數(shù)改造成偶數(shù)！另一個(gè)例子考古學(xué)家發(fā)現(xiàn)了一塊布，布上做有針線活，叫做“十字繡”交替地在布的兩面穿線布是一個(gè)n×m的網(wǎng)格線只能在網(wǎng)格的頂點(diǎn)處才能從布的一面穿到另一面。每一段線都覆蓋一個(gè)單位網(wǎng)格的兩條對(duì)角線之一而在繡的過(guò)程中，一針中連續(xù)的兩段線必須分處布的兩面給出布兩面的圖案（實(shí)線代表有線，虛線代表背面有線）最少需要幾針才能繡出來(lái)？一針是指針不離開(kāi)布的一次繡花過(guò)程。例如圖(b)的圖案最少需要4針。

分析抽象成圖正面的線：正邊背面的線：負(fù)邊有邊相連：連通塊每個(gè)連通塊分別求對(duì)于某個(gè)頂點(diǎn)I|正邊數(shù)-負(fù)邊數(shù)|=K>0時(shí)以該頂點(diǎn)為開(kāi)始或結(jié)束的針數(shù)>=K可以恰好為K針?biāo)蠯值加起來(lái)，除以2（每一針有兩個(gè)端點(diǎn)）最小生成樹(shù)問(wèn)題求一個(gè)連通子圖，使得邊權(quán)和最小Prim算法任意時(shí)刻的中間結(jié)果都是一棵樹(shù)從一個(gè)點(diǎn)開(kāi)始每次都花最小的代價(jià)，用一條加進(jìn)一個(gè)新點(diǎn)問(wèn)題：這樣做是對(duì)的嗎？如何快速找到這個(gè)“最小代價(jià)”？Prim算法的正確性換一種說(shuō)法如果存在一個(gè)MST，包含當(dāng)前所有邊則也存在一個(gè)MST,它包含最小代價(jià)邊(u,v)反證法！假設(shè)存在這樣的MST當(dāng)前結(jié)點(diǎn)集為S，剩下的結(jié)點(diǎn)集為T(mén)由于在MST中S-T連通一定有跨越S-T的某邊(u’,v’)它不是最小代價(jià)邊(u,v)刪除(u’,v’)，加入(u,v)，S和T分別連通，且S-T通過(guò)(u,v)連通得到了一個(gè)更小的MST！快速找到最小代價(jià)需要借助數(shù)據(jù)結(jié)構(gòu)！我們的算法要求快速取/刪除最小值（邊權(quán)）允許插入邊（加入新點(diǎn)時(shí)插入它的關(guān)接邊）抽象數(shù)據(jù)類(lèi)型：優(yōu)先隊(duì)列！經(jīng)典實(shí)現(xiàn)：堆！Prim算法框架初始化，樹(shù)僅含一個(gè)任意一點(diǎn)v0把v0的鄰邊插入堆fori:=1ton-1dobegin

從堆中取出最小值，設(shè)邊為(u’,v’)，v’為新點(diǎn)

(u’,v’)加入生成樹(shù)中

v’和它所有不在樹(shù)中的鄰居組成的邊插入堆end;每次取最小值為O(logm)總時(shí)間復(fù)雜度為O(nlogm)Kruskal算法任意時(shí)刻的中間結(jié)果是一個(gè)森林從n個(gè)點(diǎn)的集合開(kāi)始每次選不產(chǎn)生圈的前提下權(quán)最小的邊加入問(wèn)題：這樣做是對(duì)的嗎？如何快速的判斷是否產(chǎn)生圈Kruskal算法的正確性把一個(gè)二元組(E,I)叫做一個(gè)子集系統(tǒng)，如果滿(mǎn)足：1．E是一個(gè)非空集合2．I是E的一個(gè)子集族，它在包含運(yùn)算下封閉，即I的每個(gè)元素a都是E的一個(gè)子集，并對(duì)于a的任何子集a’，a’一定也是I的元素。3．給E中每個(gè)元素e賦予一個(gè)正權(quán)w(e)?？紤]至少有一條邊的帶權(quán)無(wú)向連通圖G它的邊集為E它的所有生成森林的集合為I則(E,I)是一個(gè)子集系統(tǒng)，稱(chēng)為生成森林子集系統(tǒng)E非空，所以滿(mǎn)足條件1生成森林是E的一個(gè)邊集，而且其生成子圖仍是生成森林，滿(mǎn)足2G是帶權(quán)的，所以滿(mǎn)足3。

子集優(yōu)化問(wèn)題極大獨(dú)立集把I中的元素都稱(chēng)為獨(dú)立集對(duì)于I中的元素a，如果不存在I中的另一個(gè)元素a’使得a是a’的真子集，則稱(chēng)a是極大獨(dú)立集。該極大獨(dú)立集的基數(shù)為它包含的元素個(gè)數(shù)在剛才介紹的子集系統(tǒng)中，G的所有生成樹(shù)就是所有的極大獨(dú)立集。所有極大獨(dú)立集具有相同的基數(shù)|V|-1。其中|V|為G的頂點(diǎn)數(shù)。子集優(yōu)化問(wèn)題在子集系統(tǒng)(E,I)中選取一個(gè)元素S∈I，使得w(S)最大（定義w(S)為S中所有元素的權(quán)和）子集優(yōu)化問(wèn)題的貪心算法貪心算法先把E中元素按照權(quán)值從大到小排序?yàn)閑1,e2,…令集合S=空集然后每次嘗試著把e1,e2,…，添加到S里面如果添加之后S仍是獨(dú)立集，則添加成功如果S不是獨(dú)立集，則由定義知以后無(wú)論怎樣繼續(xù)添加元素，得到的集合都不可能重新成為獨(dú)立集，因此撤消此添加操作。Kruskal算法是生成森林子集系統(tǒng)的貪心算法！貪心算法在什么子集系統(tǒng)下是的對(duì)的呢？定理貪心算法正確，當(dāng)且僅當(dāng)這個(gè)系統(tǒng)的極大獨(dú)立集具有相同的基數(shù)滿(mǎn)足條件的子集系統(tǒng)稱(chēng)為“矩陣胚(matroid)”快速判斷是否產(chǎn)生圈需要借助數(shù)據(jù)結(jié)構(gòu)！我們的算法要求判斷兩個(gè)點(diǎn)是否在同一棵樹(shù)中產(chǎn)生圈當(dāng)且僅當(dāng)此邊連接同一樹(shù)中的點(diǎn)！快速把兩棵樹(shù)合并加邊意味著兩棵樹(shù)合為一棵抽象數(shù)據(jù)類(lèi)型：并查集！經(jīng)典實(shí)現(xiàn)：森林并查集的森林實(shí)現(xiàn)森林中的每棵樹(shù)表示不同的集合樹(shù)的形態(tài)并不重要，有意義的只是“哪些元素在樹(shù)中”并查集的操作查找用樹(shù)根作為集合的標(biāo)識(shí)不斷的找父親，最終將找到樹(shù)根要找多少次父親？和樹(shù)的高度有關(guān)！怎樣減少樹(shù)的高度？找到樹(shù)根后沿途把路徑上的結(jié)點(diǎn)的父親設(shè)為根專(zhuān)門(mén)名稱(chēng)：路徑壓縮兩元素所在的樹(shù)根相同，則二者屬于同一集合合并其中一棵樹(shù)成為另一棵樹(shù)樹(shù)根的子樹(shù)誰(shuí)成為誰(shuí)的子樹(shù)？注意樹(shù)的高度！啟發(fā)式合并時(shí)間復(fù)雜度：幾乎都為常數(shù)！并查集的實(shí)現(xiàn)回憶剛才用到了什么信息？查找：“不斷的找父親”…“沿途設(shè)置結(jié)點(diǎn)的父親為樹(shù)根”合并：“把一棵樹(shù)的父親設(shè)置為另一棵樹(shù)的樹(shù)根”只有“父親”信息！父親表示法！father:array[1..maxn]ofinteger;根結(jié)點(diǎn)root滿(mǎn)足father[root]:=root查找：whilefather[p]<>pdop:=father[p];……?合并：ifheight(p1)<height(p2)thenfather[p1]:=p2Kruskal算法框架把所有邊按照權(quán)值從小到大排序?yàn)閑1,e2,…初始化n個(gè)集合，Si={i}size:=0;fori:=1tomdoifei的兩個(gè)端點(diǎn)u,v不在同一個(gè)集合thenbegin

合并Su和Svinc(size);ifsize=n–1thenbreak;end;最壞情況循環(huán)執(zhí)行m次，判斷約O(1)如果輸入已經(jīng)排序好，則總時(shí)間復(fù)雜度為O(m)，否則為O(mlogm)最短路問(wèn)題問(wèn)題描述：給加權(quán)圖GSSSP：求給定起點(diǎn)s到其他所有點(diǎn)的最短路APSP：求每?jī)蓪?duì)點(diǎn)的最短路算法標(biāo)號(hào)設(shè)定類(lèi)：dijkstra標(biāo)號(hào)修正類(lèi)：bellman-ford動(dòng)態(tài)規(guī)劃類(lèi)：floyd-warshall變形與應(yīng)用舉例SSSP(Dijkstra算法)核心思想：按路徑遞增的次序產(chǎn)生最短路徑的算法

1)找到圖中最短的路徑，設(shè)為（v,vj）,將j設(shè)為已標(biāo)號(hào)的點(diǎn)

2)找下一條次短的路徑，假設(shè)終點(diǎn)為k,將k設(shè)為已標(biāo)號(hào)的點(diǎn),那么要么是（v,vk）要么是（v,vj,vk）,若經(jīng)過(guò)vj,將j設(shè)為已檢查的點(diǎn),放入集合.3)以次短路徑出發(fā)找第三短的路徑,類(lèi)似第二步的方法.4)按上述方法一直到所有的頂點(diǎn)被檢查過(guò),則從v到其他頂點(diǎn)的最短路徑求出.Dijkstra算法令d’(u)=min{d[v]+w(v,u)|v存在}，設(shè)中最小的元素為i，則令（即求出了i的最短路長(zhǎng)度），并根據(jù)d[i]來(lái)對(duì)進(jìn)行更新。每次求出一個(gè)d值，重復(fù)n次就可以得到所有點(diǎn)的最短路徑長(zhǎng)度。下面是Dijkstra算法的偽代碼：ProcSSSP_Dijkstra(start:integer);Fori:=1tondod’(i):=∞;d’(start):=0;Fork:=1TonDo【i:=GetMin(ProcSSSP_Dijkstra(start:integer);Fori:=1tondod’(i):=∞;d’(start):=0;Fork:=1TonDo【i:=GetMin();{取出d’中值最小的結(jié)點(diǎn)i}d[i]:=d’(i);Delete(i,d’);{令d[i]等于d’(i)，并將i從d’中刪除}Foreachnodeuexistedge(i,u)【{對(duì)每條從i連出的邊進(jìn)行檢查}Ifd’(u)<d[i]+w(i,u)Thend’(u):=d[i]+w(i,u);】{根據(jù)d[i]對(duì)d’(u)進(jìn)行更新}】End;Dijkstra算法適用條件:所有邊的權(quán)值非負(fù)定理2每當(dāng)結(jié)點(diǎn)u插入集合S時(shí)，有d[u]=w(s,u)成立。效率:用一維數(shù)組來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列Q，O(V2)，適用于中等規(guī)模的稠密圖二叉堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列Q，O((E+V)logV)，適用于稀疏圖用Fibonacci堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列Q的話(huà)，O(VlogV)，可惜編程復(fù)雜度過(guò)高，理論價(jià)值遠(yuǎn)大于實(shí)用價(jià)值Bellman-Ford算法Bellman-Ford算法流程分為三個(gè)階段：(1)初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值

d[v]←+∞,d[s]←0;(2)迭代求解：反復(fù)對(duì)邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V中的每個(gè)頂點(diǎn)的最短距離估計(jì)值逐步逼近其最短距離；（運(yùn)行|v|-1次）(3)檢驗(yàn)負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個(gè)端點(diǎn)是否收斂。如果存在未收斂的頂點(diǎn)，則算法返回false，表明問(wèn)題無(wú)解；否則算法返回true，并且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在

d[v]中。Bellman-Ford算法Bellman-Ford算法運(yùn)用了松弛技術(shù)，對(duì)每一結(jié)點(diǎn)v∈V，逐步減小從源s到v的最短路徑的估計(jì)值d[v]直至其達(dá)到實(shí)際最短路徑的權(quán)w(s,v)，如果圖中存在負(fù)權(quán)回路，算法將會(huì)報(bào)告最短路不存在。Bellman-Ford(G,w,s)：boolean//圖G，邊集函數(shù)

w，s為源點(diǎn)

foreachvertexv∈V（G）

do//初始化

1階段

d[v]←+∞

d[s]←0;//1階段結(jié)束

fori=1to|v|-1do//2階段開(kāi)始，雙重循環(huán)。

foreachedge（u,v）∈E(G)do//邊集數(shù)組要用到，窮舉每條邊。

Ifd[v]>d[u]+w(u,v)then//松弛判斷

d[v]=d[u]+w(u,v)//松弛操作

2階段結(jié)束

foreachedge（u,v）∈E(G)do

Ifd[v]>d[u]+w(u,v)then

Exitfalse

ExittrueBellman-Ford算法適用條件:任意邊權(quán)為實(shí)數(shù)的圖Bellman-Ford算法的思想基于以下事實(shí)：“兩點(diǎn)間如果有最短路，那么每個(gè)結(jié)點(diǎn)最多經(jīng)過(guò)一次。也就是說(shuō)，這條路不超過(guò)n-1條邊?！保ㄈ绻粋€(gè)結(jié)點(diǎn)經(jīng)過(guò)了兩次，那么我們走了一個(gè)圈。如果這個(gè)圈的權(quán)為正，顯然不劃算；如果是負(fù)圈，那么最短路不存在；如果是零圈，去掉不影響最優(yōu)值）Bellman-Ford算法的運(yùn)行時(shí)間為O(VE)。很多時(shí)候，我們的算法并不需要運(yùn)行|V|-1次就能得到最優(yōu)值。對(duì)于一次完整的第3-4行操作，要是一個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值也沒(méi)能更新，就可以退出了。經(jīng)過(guò)優(yōu)化后，對(duì)于多數(shù)情況而言，程序的實(shí)際運(yùn)行效率將遠(yuǎn)離O(VE)而變?yōu)镺(kE)，其中k是一個(gè)比|V|小很多的數(shù)。SPFA(ShortestPathFasterAlgorithm)SPFA對(duì)Bellman-Ford算法優(yōu)化的關(guān)鍵之處在于意識(shí)到：只有那些在前一遍松弛中改變了距離估計(jì)值的點(diǎn)，才可能引起他們的鄰接點(diǎn)的距離估計(jì)值的改變。因此，用一個(gè)先進(jìn)先出的隊(duì)列來(lái)存放被成功松弛的頂點(diǎn)。初始時(shí)，源點(diǎn)s入隊(duì)。當(dāng)隊(duì)列不為空時(shí)，取出對(duì)首頂點(diǎn)，對(duì)它的鄰接點(diǎn)進(jìn)行松弛。如果某個(gè)鄰接點(diǎn)松弛成功，且該鄰接點(diǎn)不在隊(duì)列中，則將其入隊(duì)。經(jīng)過(guò)有限次的松弛操作后，隊(duì)列將為空，算法結(jié)束。SPFA算法的實(shí)現(xiàn)，需要用到一個(gè)先進(jìn)先出的隊(duì)列

queue和一個(gè)指示頂點(diǎn)是否在隊(duì)列中的標(biāo)記數(shù)組

mark。定理4在平均情況下，SPFA算法的期望時(shí)間復(fù)雜度為O(E)。證明：上述算法每次取出隊(duì)首結(jié)點(diǎn)u，并訪問(wèn)u的所有臨結(jié)點(diǎn)的復(fù)雜度為O(d)，其中d為點(diǎn)u的出度。運(yùn)用均攤分析的思想，對(duì)于|V|個(gè)點(diǎn)|E|條邊的圖，點(diǎn)的平均出度為E/V，所以每處理一個(gè)點(diǎn)的復(fù)雜度為O(E/V)。假設(shè)結(jié)點(diǎn)入隊(duì)次數(shù)為h，顯然h隨圖的不同而不同。但它僅與邊權(quán)值分布有關(guān)。我們?cè)O(shè)h=kV，則算法SPFA的時(shí)間復(fù)雜度為在平均的情況下，可以將k看成一個(gè)比較小的常數(shù)，所以SPFA算法在一般情況下的時(shí)間復(fù)雜度為O(E)。（證畢）SPFA算法適用條件任意邊權(quán)為實(shí)數(shù)的圖定理3只要最短路徑存在，上述SPFA算法必定能求出最小值。證明：每次將點(diǎn)放入隊(duì)尾，都是經(jīng)過(guò)松弛操作達(dá)到的。換言之，每次的優(yōu)化將會(huì)有某個(gè)點(diǎn)v的最短路徑估計(jì)值d[v]變小。所以算法的執(zhí)行會(huì)使d越來(lái)越小。由于我們假定圖中不存在負(fù)權(quán)回路，所以每個(gè)結(jié)點(diǎn)都有最短路徑值。因此，算法不會(huì)無(wú)限執(zhí)行下去，隨著d值的逐漸變小，直到到達(dá)最短路徑值時(shí)，算法結(jié)束，這時(shí)的最短路徑估計(jì)值就是對(duì)應(yīng)結(jié)點(diǎn)的最短路徑值。（證畢）SPFA算法

設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來(lái)保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)u，并且用u點(diǎn)當(dāng)前的最短路徑估計(jì)值對(duì)離開(kāi)u點(diǎn)所指向的結(jié)點(diǎn)v進(jìn)行松弛操作，如果v點(diǎn)的最短路徑估計(jì)值有所調(diào)整，且v點(diǎn)不在當(dāng)前的隊(duì)列中，就將v點(diǎn)放入隊(duì)尾。這樣不斷從隊(duì)列中取出結(jié)點(diǎn)來(lái)進(jìn)行松弛操作，直至隊(duì)列空為止。SPFA(G,w,s)1.INITIALIZE-SINGLE-SOURCE(G,s)2.INITIALIZE-QUEUE(Q)3.ENQUEUE(Q,s)4.WhileNotEMPTY(Q)5.Dou←DLQUEUE(Q)6.For每條邊(u,v)E[G]7.Dotmp←d[v]8.Relax(u,v,w)9.If(d[v]<tmp)and(v不在Q中)10.ENQUEUE(Q,v)

我們用數(shù)組d記錄每個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值，而且用鄰接表來(lái)存儲(chǔ)圖G。我們采取的方法是動(dòng)態(tài)逼近法：Car的旅行路線又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每個(gè)城市都有四個(gè)飛機(jī)場(chǎng)，分別位于一個(gè)矩形的四個(gè)頂點(diǎn)上，同一個(gè)城市中兩個(gè)機(jī)場(chǎng)之間有一條筆直的高速鐵路，第i個(gè)城市中高速鐵路的單位里程價(jià)格為T(mén)i，任意兩個(gè)不同城市的機(jī)場(chǎng)之間均有航線，所有航線單位里程的價(jià)格均為t。那么Car應(yīng)如何安排到城市B的路線才能盡可能的節(jié)省花費(fèi)昵？她發(fā)現(xiàn)這并不是一個(gè)簡(jiǎn)單的問(wèn)題，于是她來(lái)向你請(qǐng)教。約束條件輸入第一行為一個(gè)正整數(shù)n(0≤n≤10)，表示有n組測(cè)試數(shù)據(jù)。 每組的第一行有四個(gè)正整數(shù)s，t，A，B。s（0＜S≤100）表示城市的個(gè)數(shù)，t表示飛機(jī)單位里程的價(jià)格，A，B分別為城市A，B的序號(hào)，（1≤A，B≤S）。 接下來(lái)有s行，其中第i行均有7個(gè)正整數(shù)xi1，yi1，xi2，yi2，xi3，yi3，Ti，這當(dāng)中的(xi1，yi1-)，(xi2，yi2)，(xi3，yi3)分別是第I個(gè)城市中任意三個(gè)機(jī)場(chǎng)的坐標(biāo)，Ti為第i個(gè)城市高速鐵路單位里程的價(jià)格。輸出 共有n行，每行一個(gè)數(shù)據(jù)對(duì)應(yīng)測(cè)試數(shù)據(jù)。分析1、計(jì)算兩點(diǎn)間的歐氏距離2、計(jì)算每個(gè)機(jī)場(chǎng)的坐標(biāo)序列3、使用Dijkstra算法計(jì)算最小費(fèi)用SSSP：權(quán)非負(fù)的情形求1到所有點(diǎn)的距離d[1]=0d[2]<=3,d[4]<=4d[2]=3.為什么？每次固定d的最小值標(biāo)號(hào)設(shè)定！怎樣取最小值？堆！名稱(chēng)：dijkstra和Prim算法很類(lèi)似Prim:邊最小值dijkstra:d最小值中間結(jié)果：最短路樹(shù)！時(shí)間復(fù)雜度O((m+n)logm)一個(gè)例子給出一個(gè)帶權(quán)無(wú)向圖G邊權(quán)為1…1000的整數(shù)對(duì)于v0到v1的任意一條簡(jiǎn)單路p定義s(p)為p上所有邊權(quán)的最大公約數(shù)考慮v0到v1的所有路p1,p2,…求所有s(p1),s(p2),…的最小公倍數(shù)模型？最短路？路徑長(zhǎng)度定義不再是權(quán)和，而是…dijkstra算法還能用嗎？SSSP：權(quán)任意的情形最短路有可能不存在！什么時(shí)候不存在？有負(fù)圈！標(biāo)號(hào)設(shè)定標(biāo)號(hào)修正仍然有標(biāo)號(hào)d[i]<=k但是標(biāo)號(hào)d[i]無(wú)法固定，只能不斷更新新算法如有最短路，則每個(gè)頂點(diǎn)最多經(jīng)過(guò)一次即：這條路不超過(guò)n-1條邊迭代！依次考慮1,2,3…n-1條邊的情形SSSP：bellman-ford算法依次考慮邊長(zhǎng)度不超過(guò)1,2…n-1的路考慮長(zhǎng)度不超過(guò)1,2,3…k-1的路后，標(biāo)號(hào)為d[]長(zhǎng)度為k的路可以由不超過(guò)1,2,…k-1的路增加一條邊得到：fork:=1ton-1dofor每條邊(u,v)doif(d[u]<∞)and(d[v]>d[u]+w(u,v))thend[v]:=d[u]+w(u,v)核心：標(biāo)號(hào)修正過(guò)程（松弛操作）時(shí)間復(fù)雜度：O(nm)改進(jìn)的終止條件：d都不改變加速：用dijkstra得到初始d[]APSP:基本分析設(shè)d[i，j，k]是在只允許經(jīng)過(guò)結(jié)點(diǎn)[1…k]的情況下i到j(luò)的最短路長(zhǎng)度則它有兩種情況（想一想，為什么）：如果最短路經(jīng)過(guò)點(diǎn)k，那么d[i，j，k]應(yīng)該等于d[i，k，k-1]+d[k，j，k-1]；如果最短路不經(jīng)過(guò)點(diǎn)k，那么d[i，j，k]應(yīng)該等于d[i，j，k-1]。綜合起來(lái)d[i，j，k]=min{d[i，k，k-1]+d[k，j，k-1]，d[i，j，k-1]}邊界條件是d[i，j，0]=w(i，j)（不存在的邊權(quán)為∞）floyd-warshall算法基本的動(dòng)態(tài)規(guī)劃把k放外層循環(huán)，可以節(jié)省內(nèi)存對(duì)于每個(gè)k，計(jì)算每?jī)牲c(diǎn)的目前最短路fork:=1tondofori:=1tondoforj:=1tondoif(d[i,k]<∞)and(d[k,j]<∞)and(d[i,k]+d[k,j]<d[i,j])thend[i,j]:=d[i,k]+d[k,j]一定要背下來(lái)！時(shí)間復(fù)雜度：O(n3)用途：預(yù)處理！選址問(wèn)題--中心問(wèn)題某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示．問(wèn)應(yīng)設(shè)在那個(gè)區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短．解析求出距離矩陣D=．

關(guān)鍵工程在大型工程的施工前，我們把整個(gè)工程劃分為若干個(gè)子工程，并把這些子工程編號(hào)為1、2、……、N；這樣劃分之后，子工程之間就會(huì)有一些依賴(lài)關(guān)系，即一些子工程必須在某些子工程完成之后才能施工。由于子工程之間有相互依賴(lài)關(guān)系，因此有兩個(gè)任務(wù)需要我們?nèi)ネ瓿桑菏紫?，我們需要?jì)算整個(gè)工程最少的完成時(shí)間；同時(shí)，由于一些不可預(yù)測(cè)的客觀因素會(huì)使某些子工程延期，因此我們必須知道哪些子工程的延期會(huì)影響整個(gè)工程的延期，我們把有這種特征的子工程稱(chēng)為關(guān)鍵子工程，因此第二個(gè)任務(wù)就是找出所有的關(guān)鍵子工程，以便集中精力管理好這些子工程，盡量避免這些子工程延期，達(dá)到用最快的速度完成整個(gè)工程。為了便于編程，現(xiàn)在我們假設(shè)：（1）根據(jù)預(yù)算，每一個(gè)子工程都有一個(gè)完成時(shí)間。（2）子工程之間的依賴(lài)關(guān)系是：部分子工程必須在一些子工程完成之后才開(kāi)工。（3）只要滿(mǎn)足子工程間的依賴(lài)關(guān)系，在任何時(shí)刻可以有任何多個(gè)子工程同時(shí)在施工，也既同時(shí)施工的子工程個(gè)數(shù)不受限制。（4）整個(gè)工程的完成是指：所有子工程的完成。示例1序號(hào)完成時(shí)間子工程1子工程2子工程3子工程4子工程5子工程150000子工程240000子工程3120000子工程471100子工程521111約束條件輸入：第1行為N，N是子工程的總個(gè)