筆者從基本儲存方法、DFS和BFS、無向圖、最小生成樹、最短路徑以及活動網絡(AOV、AOE)六個方面詳細介紹C++圖的應用。之前我們已經介紹過了基本儲存方法、DFS和BFS、無向圖以及最小生成樹，今天我們介紹最短路徑。

　　最短路徑

　　最短路徑恐怕是圖的各種算法中最能吸引初學者眼球的了——在地圖上找一條最短的路或許每個人都曾經嘗試過。下面我們用計算機來完成我們曾經的“愿望”。

　　在圖的算法中有個有趣的現象，就是問題的規模越大，算法就越簡單。圖是個復雜的結構，對于一個特定問題，求解特定頂點的結果都會受到其他頂點的影響——就好比一堆互相碰撞的球體，要求解特定球體的狀態，就必須考慮其他球體的狀態。既然每個頂點都要掃描，如果對所有的頂點都求解，那么算法就非常的簡單——無非是遍歷嗎。然而，當我們降低問題規模，那很自然的，我們希望算法的規模也降低——如果不降低，不是殺雞用牛刀?但是，正是由于圖的復雜性，使得這種降低不容易達到，因此，為了降低算法的規模，使得算法就復雜了。

　　在下面的介紹中，清楚了印證了上面的結論。人的認知過程是從簡單到復雜，雖然表面看上去，求每對頂點之間的最短路徑要比特定頂點到其他頂點之間的最短路徑復雜，但是，就像上面說的，本質上，前者更為簡單。下面的介紹沒有考慮歷史因素(就是指哪個算法先提出來)，也沒有考慮算法提出者的真實想法(究竟是誰參考了或是沒參考誰)，只是從算法本身之間的聯系來做一個闡述，如有疏漏，敬請原諒。

　　準備工作

　　一路走下來，圖類已經很“臃腫”了，為了更清晰的說明問題，需要“重起爐灶另開張”，同時也是為了使算法和儲存方法分開，以便于復用。

　　首先要為基本圖類添加幾個接口。

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;  
}  
}; 

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

Network<char, int, Link<char, int> > a(100);  
//插入點、邊……  
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;  
}; 

　　發現有了構造函數真好，算法的結果數組的初始化和算法本身分開了，這樣一來，算法的基本步驟就很容易看清楚了。

#p#

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

　　從v1到v2的路徑要么是v1->v2，要么中間經過了若干頂點。顯然我們要求的是這些路徑中最短的一條。這樣一來，問題就很好解決了——最初都是源點到目的點，然后依次添加頂點，使得路徑逐漸縮短，頂點都添加完了，算法就結束了。

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算法的思想，不能使算法的時間復雜度從O(n3)降到預期的O(n2)，只是空間復雜度從O(n2)降到了O(n)，但這也是應該的，因為只需要原來結果數組中的一行。因此，我并不覺得這個算法是解決“邊上權值為任意值的單源最短路徑問題”而專門提出來的，是Dijkstra算法的“推廣”版本，他只是Floyed算法的退化版本。

　　顯然，Floyed算法是經過N次N2條邊迭代而產生最短路徑的;如果我們想把時間復雜度從O(n3) 降到預期的O(n2)，就必須把N次迭代的N2條邊變為N條邊，也就是說每次參與迭代的只有一條邊——問題是如何找到這條邊。

　　先看看邊的權值非負的情況。假設從頂點0出發，到各個頂點的距離是a1,a2……，那么，這其中的最短距離an必定是從0到n號頂點的最短距離。這是因為，如果an不是從0到n號頂點的最短距離，那么必然是中間經過了某個頂點;但現在邊的權值非負，一個比現在這條邊還長的邊再加上另一條非負的邊，是不可能比這條邊短的。從這個原理出發，就能得出Dijkstra算法，注意，這個和Prim算法極其相似，不知道誰參考了誰;但這也是難免的事情，因為他們的原理是一樣的。

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);  
} 

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

　　特定兩個頂點之間的最短路徑(A*算法)

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

　　讓我們先來看看Dijkstra算法求特定兩個頂點之間的最短路徑的時間復雜度究竟是多少。顯然，在上面的void ShortestPath(const name& vex1, const name& vex2)中，當S[v2]==true時，算法就可以中止了。假設兩個頂點之間直接的路徑是他們之間的路徑最短的(不需要經過其他中間頂點)，并且這個路徑長度是源點到所有目的點的最短路徑中最短的，那么***次迭代的時候，就可以得到結果了。也就是說是O(n)。然而當兩個頂點的最短路徑需要經過其他頂點，或者路徑長度不是源點到未求出最短路徑的目的點的最短路徑中最短的，那就要再進行若干次迭代，對應的，時間復雜度就變為O(2n)、O(3n)……到了***才求出來(迭代了N-1次)的就是O(n2)。

　　很明顯的，迭代次數是有下限的，最短路徑上要經過多少個頂點，至少就要迭代多少次，我們只能使得最終的迭代次數接近最少需要的次數。如果再要減低算法的時間復雜度，我們只能想辦法把搜索范圍的O(n)變為O(1)，這樣，即使迭代了N-1次才得到結果，那時間復雜度仍為O(n)。但這個想法實現起來卻是困難重重。

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

　　現在讓我們給圖添加一個附加條件——兩點之間直線最短，就是說如果v1和v2之間有直通的路徑(不經過其他頂點)，那么這條路徑就是他們之間的最短路徑。這樣一來，如果求的是v1能夠直接到達的頂點的最短路徑，時間復雜度就是O(1)了，顯然比原來***的O(n)(這里實際上是O(logN))提高了效率。

　　這個變化的產生，是因為我們添加了“兩點之間直線最短”這樣的附加條件，實際上就是引入一個判斷準則，把原來盲目的O(n)搜索降到了O(1)。這個思想就是A*算法的思想。關于A*算法更深入的介紹，恕本人資料有限，不能滿足大家了。有興趣的可以到網上查查，這方面的中文資料實在太少了，大家做好看E文的準備吧。

　　不同于現有的教科書，我把求最短路徑的算法的介紹順序改成了上面的樣子。我認為這個順序才真正反映了問題的本質——當減低問題規模時，為了降低算法的時間復雜度，應該想辦法縮小搜索范圍。而縮小搜索范圍，都用到了一個思想——盡可能的向接近***結果的方向搜索，這就是貪婪算法的應用。

　　如果反向看一遍算法的演化，我們還能得出新的結論。Dijkstra算法實際上不用做n2次搜索、比較和修改，當求出最短路徑的頂點后，搜索范圍已經被縮小了，只是限于儲存結構，這種范圍的縮小并沒有體現出來。如果我們使得這種范圍縮小直接體現出來，那么，用n次Dijkstra算法代替Floyed算法就能帶來效率上的提升。A*算法也是如此，如果用求n點的A*算法來代替Dijkstra算法，也能帶來效率的提升。

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

【編輯推薦】

1. 經典四講貫通C++排序之一 插入排序
2. c++編程常用工具
3. 給C++初學者的50個忠告
4. C++獲取當前路徑實現技巧分享
5. 程序員必看 c++筆試題匯總