六講貫通C++圖的應用之五 最短路徑(1)

筆者從基本儲存方法、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;  
}; 

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