六讲贯通C++图的应用之五 最短路径
美丽的泡沫 2011-04-11
笔者从基本储存方法、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;
}; 发现有了构造函数真好，算法的结果数组的初始化和算法本身分开了，这样一来，算法的基本步骤就很容易看清楚了。
所有顶点之间的最短路径(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文的准备吧。
不同于现有的教科书，我把求最短路径的算法的介绍顺序改成了上面的样子。我认为这个顺序才真正反映了问题的本质――当减低问题规模时，为了降低算法的时间复杂度，应该想办法缩小搜索范围。而缩小搜索范围，都用到了一个思想――尽可能的向接近最后结果的方向搜索，这就是贪婪算法的应用。
