六讲贯通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;  
}; 

发现有了构造函数真好，算法的结果数组的初始化和算法本身分开了，这样一来，算法的基本步骤就很容易看清楚了。