| 了或是没参考谁），只是从算法本身之间的联系来做一个阐述，如有疏漏，敬请原谅。
准备工作
一路走下来，图类已经很“臃肿”了，为了更清晰的说明问题，需要“重起炉灶另开张”，同时也是为了使算法和储存方法分开，以便于复用。
首先要为基本图类添加几个接口。
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<edge>::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<name, dist, mem>* 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<name, dist, mem>* 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]
|
