筆者從基本儲(chǔ)存方法、DFS和BFS、無(wú)向圖、最小生成樹、最短路徑以及活動(dòng)網(wǎng)絡(luò)(AOV、AOE)六個(gè)方面詳細(xì)介紹C++圖的應(yīng)用。之前我們已經(jīng)介紹過(guò)了基本儲(chǔ)存方法、DFS和BFS、無(wú)向圖以及最小生成樹，今天我們介紹最短路徑。

　　最短路徑

　　最短路徑恐怕是圖的各種算法中最能吸引初學(xué)者眼球的了——在地圖上找一條最短的路或許每個(gè)人都曾經(jīng)嘗試過(guò)。下面我們用計(jì)算機(jī)來(lái)完成我們?cè)?jīng)的“愿望”。

　　在圖的算法中有個(gè)有趣的現(xiàn)象，就是問(wèn)題的規(guī)模越大，算法就越簡(jiǎn)單。圖是個(gè)復(fù)雜的結(jié)構(gòu)，對(duì)于一個(gè)特定問(wèn)題，求解特定頂點(diǎn)的結(jié)果都會(huì)受到其他頂點(diǎn)的影響——就好比一堆互相碰撞的球體，要求解特定球體的狀態(tài)，就必須考慮其他球體的狀態(tài)。既然每個(gè)頂點(diǎn)都要掃描，如果對(duì)所有的頂點(diǎn)都求解，那么算法就非常的簡(jiǎn)單——無(wú)非是遍歷嗎。然而，當(dāng)我們降低問(wèn)題規(guī)模，那很自然的，我們希望算法的規(guī)模也降低——如果不降低，不是殺雞用牛刀?但是，正是由于圖的復(fù)雜性，使得這種降低不容易達(dá)到，因此，為了降低算法的規(guī)模，使得算法就復(fù)雜了。

　　在下面的介紹中，清楚了印證了上面的結(jié)論。人的認(rèn)知過(guò)程是從簡(jiǎn)單到復(fù)雜，雖然表面看上去，求每對(duì)頂點(diǎn)之間的最短路徑要比特定頂點(diǎn)到其他頂點(diǎn)之間的最短路徑復(fù)雜，但是，就像上面說(shuō)的，本質(zhì)上，前者更為簡(jiǎn)單。下面的介紹沒有考慮歷史因素(就是指哪個(gè)算法先提出來(lái))，也沒有考慮算法提出者的真實(shí)想法(究竟是誰(shuí)參考了或是沒參考誰(shuí))，只是從算法本身之間的聯(lián)系來(lái)做一個(gè)闡述，如有疏漏，敬請(qǐng)?jiān)彙?/P>

　　準(zhǔn)備工作

　　一路走下來(lái)，圖類已經(jīng)很“臃腫”了，為了更清晰的說(shuō)明問(wèn)題，需要“重起爐灶另開張”，同時(shí)也是為了使算法和儲(chǔ)存方法分開，以便于復(fù)用。

　　首先要為基本圖類添加幾個(gè)接口。

template <class name, class dist, class mem>  
class Network  
{  
public:  
int find(const name& v) { int n; if (!data.find(v, n)) return -1; return n; }  
dist& getE(int m, int n) { return data.getE(m, n); }  
const dist& NoEdge() { return data.NoEdge; }  
};  
template <class name, class dist>  
class AdjMatrix  
{  
public:  
dist& getE(int m, int n) { return edge[m][n]; }  
};  
template <class name, class dist>  
class Link  
{  
public:  
dist& getE(int m, int n)  
{  
for (list::iterator iter = vertices[m].e->begin();  
iter != vertices[m].e->end() && iter->vID < n; iter++);  
if (iter == vertices[m].e->end()) return NoEdge;  
if (iter->vID == n) return iter->cost;  
return NoEdge;  
}  
}; 

　　然后就是為了最短路徑算法“量身定做”的“算法類”。求某個(gè)圖的最短路徑時(shí)，將圖綁定到算法上，例如這樣：

Network<char, int, Link<char, int> > a(100);  
//插入點(diǎn)、邊……  
Weight<char, int, Link<char, int> > b(&a);  
 
#include "Network.h"  
template <class name, class dist, class mem>  
class Weight  
{  
public:  
Weight(Network* G) : G(G), all(false), N(G->vNum())  
{  
length = new dist*[N]; path = new int*[N];  
shortest = new bool[N]; int i, j;  
for (i = 0; i < N; i++)  
{  
length[i] = new dist[N]; path[i] = new int[N];  
}  
for (i = 0; i < N; i++)  
{  
shortest[i] = false;  
for (j = 0; j < N; j++)  
{  
length[i][j] = G->getE(i, j);  
if (length[i][j] != G->NoEdge()) path[i][j] = i;  
else path[i][j] = -1;  
}  
}  
}  
~Weight()  
{  
for (int i = 0; i < N; i++) { delete []length[i]; delete []path[i]; }  
delete []length; delete []path; delete []shortest;  
}  
private:  
void print(int i, int j)  
{  
if (path[i][j] == -1) cout << "No Path" << endl; return;  
cout << "Shortest Path: "; out(i, j); cout << G->getV(j) << endl;  
cout << "Path Length: " << length[i][j] << endl;  
}  
void out(int i, int j)  
{  
if (path[i][j] != i) out(i, path[i][j]);  
cout << G->getV(path[i][j]) << "->";  
}  
dist** length; int** path; bool* shortest; bool all; int N;  
Network* G;  
}; 

　　發(fā)現(xiàn)有了構(gòu)造函數(shù)真好，算法的結(jié)果數(shù)組的初始化和算法本身分開了，這樣一來(lái)，算法的基本步驟就很容易看清楚了。

#p#

　　所有頂點(diǎn)之間的最短路徑(Floyed算法)

　　從v1到v2的路徑要么是v1->v2，要么中間經(jīng)過(guò)了若干頂點(diǎn)。顯然我們要求的是這些路徑中最短的一條。這樣一來(lái)，問(wèn)題就很好解決了——最初都是源點(diǎn)到目的點(diǎn)，然后依次添加頂點(diǎn)，使得路徑逐漸縮短，頂點(diǎn)都添加完了，算法就結(jié)束了。

void AllShortestPath()//Folyed  
{  
if (all) return;  
for (int k = 0; k < N; k++)  
{  
shortest[k] = true;  
for (int i = 0; i < N; i++)  
for (int j = 0; j < N; j++)  
if (length[i][k] + length[k][j] < length[i][j])  
{  
length[i][j] = length[i][k] + length[k][j];  
path[i][j] = path[k][j];  
}  
}  
all = true;  
} 

　　單源最短路徑(Dijkstra算法)

　　仿照上面的Floyed算法，很容易的，我們能得出下面的算法：

void ShortestPath(int v1)  
{  
//Bellman-Ford  
for (int k = 2; k < N; k++)  
for (int i = 0; i < N; i++)  
for (int j = 0; j < N; j++)  
if (length[v1][j] + length[j][i] < length[v1][i])  
{  
length[v1][i] = length[v1][j] + length[j][i];  
path[v1][i] = j;  
}  
} 

　　這就是Bellman-Ford算法，可以看到，采用Floyed算法的思想，不能使算法的時(shí)間復(fù)雜度從O(n3)降到預(yù)期的O(n2)，只是空間復(fù)雜度從O(n2)降到了O(n)，但這也是應(yīng)該的，因?yàn)橹恍枰瓉?lái)結(jié)果數(shù)組中的一行。因此，我并不覺得這個(gè)算法是解決“邊上權(quán)值為任意值的單源最短路徑問(wèn)題”而專門提出來(lái)的，是Dijkstra算法的“推廣”版本，他只是Floyed算法的退化版本。

　　顯然，F(xiàn)loyed算法是經(jīng)過(guò)N次N2條邊迭代而產(chǎn)生最短路徑的;如果我們想把時(shí)間復(fù)雜度從O(n3) 降到預(yù)期的O(n2)，就必須把N次迭代的N2條邊變?yōu)镹條邊，也就是說(shuō)每次參與迭代的只有一條邊——問(wèn)題是如何找到這條邊。

　　先看看邊的權(quán)值非負(fù)的情況。假設(shè)從頂點(diǎn)0出發(fā)，到各個(gè)頂點(diǎn)的距離是a1,a2……，那么，這其中的最短距離an必定是從0到n號(hào)頂點(diǎn)的最短距離。這是因?yàn)?，如果an不是從0到n號(hào)頂點(diǎn)的最短距離，那么必然是中間經(jīng)過(guò)了某個(gè)頂點(diǎn);但現(xiàn)在邊的權(quán)值非負(fù)，一個(gè)比現(xiàn)在這條邊還長(zhǎng)的邊再加上另一條非負(fù)的邊，是不可能比這條邊短的。從這個(gè)原理出發(fā)，就能得出Dijkstra算法，注意，這個(gè)和Prim算法極其相似，不知道誰(shuí)參考了誰(shuí);但這也是難免的事情，因?yàn)樗麄兊脑硎且粯拥摹?/P>

void ShortestPath(const name& vex1, const name& vex2)//Dijkstra  
{  
int v1 = G->find(vex1); int v2 = G->find(vex2);  
if (shortest[v1]) { print(v1, v2); return; }  
bool* S = new bool[N]; int i, j, k;  
for (i = 0; i < N; i++) S[i] = false; S[v1] = true;  
for (i = 0; i < N - 1; i++)//Dijkstra Start, like Prim?  
{  
for (j = 0, k = v1; j < N; j++)  
if (!S[j] && length[v1][j] < length[v1][k]) k = j;  
S[k] = true;  
for (j = 0; j < N; j++)  
if (!S[j] && length[v1][k] + length[k][j] < length[v1][j])  
{  
length[v1][j] = length[v1][k] + length[k][j];  
path[v1][j] = k;  
}  
}  
shortest[v1] = true; print(v1, v2);  
} 

　　如果邊的權(quán)值有負(fù)值，那么上面的原則不再適用，連帶的，Dijkstra算法也就不再適用了。這時(shí)候，沒辦法，只有接受O(n3) Bellman-Ford算法了，雖然他可以降低為O(n*e)。不過(guò)，何必讓邊的權(quán)值為負(fù)值呢?還是那句話，合理的并不好用。

　　特定兩個(gè)頂點(diǎn)之間的最短路徑(A*算法)

　　其實(shí)這才是我們最關(guān)心的問(wèn)題，我們只是想知道從甲地到乙地怎么走最近，并不想知道別的——甲地到丙地怎么走關(guān)我什么事?自然的，我們希望這個(gè)算法的時(shí)間復(fù)雜度為O(n)，但是，正像從Floyed算法到Dijkstra算法的變化一樣，并不是很容易達(dá)到這個(gè)目標(biāo)的。

　　讓我們先來(lái)看看Dijkstra算法求特定兩個(gè)頂點(diǎn)之間的最短路徑的時(shí)間復(fù)雜度究竟是多少。顯然，在上面的void ShortestPath(const name& vex1, const name& vex2)中，當(dāng)S[v2]==true時(shí)，算法就可以中止了。假設(shè)兩個(gè)頂點(diǎn)之間直接的路徑是他們之間的路徑最短的(不需要經(jīng)過(guò)其他中間頂點(diǎn))，并且這個(gè)路徑長(zhǎng)度是源點(diǎn)到所有目的點(diǎn)的最短路徑中最短的，那么***次迭代的時(shí)候，就可以得到結(jié)果了。也就是說(shuō)是O(n)。然而當(dāng)兩個(gè)頂點(diǎn)的最短路徑需要經(jīng)過(guò)其他頂點(diǎn)，或者路徑長(zhǎng)度不是源點(diǎn)到未求出最短路徑的目的點(diǎn)的最短路徑中最短的，那就要再進(jìn)行若干次迭代，對(duì)應(yīng)的，時(shí)間復(fù)雜度就變?yōu)镺(2n)、O(3n)……到了***才求出來(lái)(迭代了N-1次)的就是O(n2)。

　　很明顯的，迭代次數(shù)是有下限的，最短路徑上要經(jīng)過(guò)多少個(gè)頂點(diǎn)，至少就要迭代多少次，我們只能使得最終的迭代次數(shù)接近最少需要的次數(shù)。如果再要減低算法的時(shí)間復(fù)雜度，我們只能想辦法把搜索范圍的O(n)變?yōu)镺(1)，這樣，即使迭代了N-1次才得到結(jié)果，那時(shí)間復(fù)雜度仍為O(n)。但這個(gè)想法實(shí)現(xiàn)起來(lái)卻是困難重重。

　　仍然看Dijkstra算法，***步要尋找S中的頂點(diǎn)到S外面頂點(diǎn)中最短的一條路徑，這個(gè)min運(yùn)算使用基于比較的方法的時(shí)間復(fù)雜度下限是O(longN)(使用敗者樹)，然后需要掃描結(jié)果數(shù)組的每個(gè)分量進(jìn)行修改，這里的時(shí)間復(fù)雜度就只能是O(n)了。原始的Dijkstra算法達(dá)不到預(yù)期的目的。

　　現(xiàn)在讓我們給圖添加一個(gè)附加條件——兩點(diǎn)之間直線最短，就是說(shuō)如果v1和v2之間有直通的路徑(不經(jīng)過(guò)其他頂點(diǎn))，那么這條路徑就是他們之間的最短路徑。這樣一來(lái)，如果求的是v1能夠直接到達(dá)的頂點(diǎn)的最短路徑，時(shí)間復(fù)雜度就是O(1)了，顯然比原來(lái)***的O(n)(這里實(shí)際上是O(logN))提高了效率。

　　這個(gè)變化的產(chǎn)生，是因?yàn)槲覀兲砑恿恕皟牲c(diǎn)之間直線最短”這樣的附加條件，實(shí)際上就是引入一個(gè)判斷準(zhǔn)則，把原來(lái)盲目的O(n)搜索降到了O(1)。這個(gè)思想就是A*算法的思想。關(guān)于A*算法更深入的介紹，恕本人資料有限，不能滿足大家了。有興趣的可以到網(wǎng)上查查，這方面的中文資料實(shí)在太少了，大家做好看E文的準(zhǔn)備吧。

　　不同于現(xiàn)有的教科書，我把求最短路徑的算法的介紹順序改成了上面的樣子。我認(rèn)為這個(gè)順序才真正反映了問(wèn)題的本質(zhì)——當(dāng)減低問(wèn)題規(guī)模時(shí)，為了降低算法的時(shí)間復(fù)雜度，應(yīng)該想辦法縮小搜索范圍。而縮小搜索范圍，都用到了一個(gè)思想——盡可能的向接近***結(jié)果的方向搜索，這就是貪婪算法的應(yīng)用。

　　如果反向看一遍算法的演化，我們還能得出新的結(jié)論。Dijkstra算法實(shí)際上不用做n2次搜索、比較和修改，當(dāng)求出最短路徑的頂點(diǎn)后，搜索范圍已經(jīng)被縮小了，只是限于儲(chǔ)存結(jié)構(gòu)，這種范圍的縮小并沒有體現(xiàn)出來(lái)。如果我們使得這種范圍縮小直接體現(xiàn)出來(lái)，那么，用n次Dijkstra算法代替Floyed算法就能帶來(lái)效率上的提升。A*算法也是如此，如果用求n點(diǎn)的A*算法來(lái)代替Dijkstra算法，也能帶來(lái)效率的提升。

　　但是，每一步的進(jìn)化實(shí)際上都伴隨著附加條件的引入。從Floyed到Dijkstra是邊上的權(quán)值非負(fù)，如果這個(gè)條件不成立，那么就只能退化成Bellman-Ford算法。從Dijkstra到A*是另外的判斷準(zhǔn)則的引入(本文中是兩點(diǎn)之間直線最短)，如果這個(gè)條件不成立，同樣的，只能采用不完整的Dijkstra(求到目的頂點(diǎn)結(jié)束算法)。

【編輯推薦】

1. 經(jīng)典四講貫通C++排序之一 插入排序
2. c++編程常用工具
3. 給C++初學(xué)者的50個(gè)忠告
4. C++獲取當(dāng)前路徑實(shí)現(xiàn)技巧分享
5. 程序員必看 c++筆試題匯總