圖論的基本算法

圖論基本算法長沙市雅禮中學朱全民圖圖的概念

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

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

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

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

根據(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)河西=(人,狼,羊,菜)河東=(人,狼,羊,菜)將10個頂點分別記為A1,A2,…,A10,則渡河問題化為在該圖中求一條從A1到A10的路.從圖中易得到兩條路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.圖的矩陣表示

權(quán)矩陣

無向圖G的權(quán)矩陣A是一個對稱矩陣.

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

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

-

1.鄰接表表節(jié)點

typearcptr=^arcnode;arcnode=recordadjvex:vtxptr;nextarc:arcptr;info:…{和弧有關(guān)的其他信息}end;vex=Recordvexdata:…{和頂點有關(guān)的其他信息}firstarc:arcptr;end;adjlist=array[vtxptr]ofvexnode;鄰接表123456234^135^136^236^345^12456^拓撲排序

按照有向圖給出的次序關(guān)系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點，則可以人為加上任意的次序關(guān)系。由此所得頂點的線性序列稱之為拓撲有序序列例如：對于有向圖BDAC可求得拓撲有序序列：

ABCD或ACBDBDAC對于下列有向圖不能求得它的拓撲有序序列。因為圖中存在一個回路

{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;求拓撲序列拓撲排序核心問題：給一些序關(guān)系，排出全序！一個一個排先排最大然后第二大…具體實現(xiàn)？每次取0出度點枚舉所有點嗎？0出度只可能是1出度變來的！O(n+m)神經(jīng)網(wǎng)絡

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

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

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

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

【輸入格式】

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

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

理解問題的第一步就是認真“讀題”。那么我們先來看一看這個題目涉及的問題。研究一下題目中所給的圖的一些性質(zhì)，可以發(fā)現(xiàn)如下特點：1．圖中所有的節(jié)點都有一個確定的等級，我們記作Level(i)2．圖中所有的邊都是有向的，并且從Level值為i-1的節(jié)點指向Level值為i的節(jié)點我們不妨將其抽象為“階段圖”。更一般地，我們可以發(fā)現(xiàn)所有的階段圖都是有向無環(huán)的，這樣我們可以通過拓撲排序來得到期望的處理節(jié)點的順序?？尚兴惴?/p>

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

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

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

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

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

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

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

1)找到圖中最短的路徑，設(shè)為（v,vj）,將j設(shè)為已標號的點

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

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

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

w，s為源點

foreachvertexv∈V（G）

do//初始化

1階段

d[v]←+∞

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

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

queue和一個指示頂點是否在隊列中的標記數(shù)組

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

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

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