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

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

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

　　準備工作

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

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

template
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 AdjMatrix
{
public:
dist& getE(int m, int n) { return edge[m][n]; }
};

template
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 > a(100);
//插入點、邊……
Weight > b(&a);

#include "Network.h"
template
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ù)組的初始化和算法本身分開了，這樣一來，算法的基本步驟就很容易看清楚了。

　　所有頂點之間的短路徑（Floyed算法）

　　從v1到v2的路徑要么是v1->v2，要么中間經(jīng)過了若干頂點。顯然我們要求的是這些路徑中短的一條。這樣一來，問題就很好解決了——初都是源點到目的點，然后依次添加頂點，使得路徑逐漸縮短，頂點都添加完了，算法就結(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算法的思想，不能使算法的時間復(fù)雜度從O(n3)降到預(yù)期的O(n2)，只是空間復(fù)雜度從O(n2)降到了O(n)，但這也是應(yīng)該的，因為只需要原來結(jié)果數(shù)組中的一行。因此，我并不覺得這個算法是解決“邊上權(quán)值為任意值的單源短路徑問題”而專門提出來的，是Dijkstra算法的“推廣”版本，他只是Floyed算法的退化版本。

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

　　先看看邊的權(quán)值非負的情況。假設(shè)從頂點0出發(fā)，到各個頂點的距離是a1,a2……，那么，這其中的短距離an必定是從0到n號頂點的短距離。這是因為，如果an不是從0到n號頂點的短距離，那么必然是中間經(jīng)過了某個頂點；但現(xiàn)在邊的權(quán)值非負，一個比現(xiàn)在這條邊還長的邊再加上另一條非負的邊，是不可能比這條邊短的。從這個原理出發(fā)，就能得出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);
}

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

　　特定兩個頂點之間的短路徑（A*算法）

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

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

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

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

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

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

　　總結(jié)

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

　　如果反向看一遍算法的演化，我們還能得出新的結(jié)論。Dijkstra算法實際上不用做n2次搜索、比較和修改，當(dāng)求出短路徑的頂點后，搜索范圍已經(jīng)被縮小了，只是限于儲存結(jié)構(gòu)，這種范圍的縮小并沒有體現(xiàn)出來。如果我們使得這種范圍縮小直接體現(xiàn)出來，那么，用n次Dijkstra算法代替Floyed算法就能帶來效率上的提升。A*算法也是如此，如果用求n點的A*算法來代替Dijkstra算法，也能帶來效率的提升。
　　但是，每一步的進化實際上都伴隨著附加條件的引入。從Floyed到Dijkstra是邊上的權(quán)值非負，如果這個條件不成立，那么就只能退化成Bellman-Ford算法。從Dijkstra到A*是另外的判斷準則的引入（本文中是兩點之間直線短），如果這個條件不成立，同樣的，只能采用不完整的Dijkstra（求到目的頂點結(jié)束算法）。