本文共 2126 字，大约阅读时间需要 7 分钟。

《算法导论》25.2. 《计算机算法(C++版)》5.3.

当然这个算法的实现是相当简单的，只使用了三重循环，时间复杂度为O(n^3)。但是重点是算法背后的思想，一般教材都把这个算法当做典型的图算法来讲，却没有讲到背后动态规划的思想。不过《计算机算法(C++版)》做到了这一点。此题的最优子结构很明显，假设i到j的最短路径是d<i, j>，那么明显对路径上的任一点k，有d<i, k>、d<k, j>都是最短路径。但是这样的子问题很难描述，因为两个子问题虽然明确了，但是状态并没有明确。我们想到在矩阵链乘法里，我们只要从i到j枚举k，有j-i个状态选择，因为加括号天然有序，所以我们可以保证AiAi+1…Ak和Ak+1Ak+2…Aj两个子链是不相交的，而在图中，我们不能保证这一点。解决办法是，对于每个k对应下的状态，我们让Ak(i, j)表示从i到j但不经过索引大于k的定点的最短路径的长度，这样d<i, k>的路径就不会经过d<k, j>路径中已经经过的结点，因为它们的索引大于k。当然受此启发我们也可以定义A(i, j)为表示从i到j但不经过索引小于k的定点的最短路径的长度，然后从j顶点反向遍历。

C++代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int SIZE = 101;float cost[SIZE][SIZE];float A[SIZE][SIZE];int   P[SIZE][SIZE];void PrintCost(float A[][SIZE], int n){	for(int i=1; i<=n; i++)	{		for(int j=1; j<=n; j++)		{				cout << A[i][j] << ' ';		}		cout << endl;	}}void AllPaths(float cost[][SIZE], float A[][SIZE], int n){	cout << "Graph weight:" << endl;	PrintCost(cost, n);	for(int i=1; i<=n; i++)		for(int j=1; j<=n; j++)		{			A[i][j] = cost[i][j];		}	for(int k=1; k<=n; k++)	{		for(int i=1; i<=n; i++)			for(int j=1; j<=n; j++)			{				if(A[i][k] + A[k][j] < A[i][j])				{					A[i][j] = A[i][k] + A[k][j];					P[i][j] = k;				}			} 		cout << "A" << k << ":" << endl;		PrintCost(A, n);	}}void PrintPath(int i, int j){	int k = P[i][j];		if(k == 0)		return;	PrintPath(i, k);	cout << k << "--";	PrintPath(k, j);}void PrintAllPath(int n){	for(int i=1; i<=n; i++)		for(int j=1; j<=n; j++)		{			if(j != i)			{				cout << "Path from " << i << " to " << j << ": " << endl;				cout << i << "--";				PrintPath(i, j);				cout << j << endl;			}		}}int main(){	int n = 5;	memset(A, 0, sizeof(float)*SIZE*SIZE);	memset(P, 0, sizeof(float)*SIZE*SIZE);	memset(cost, 0, sizeof(float)*SIZE*SIZE);	ifstream file("allpaths2.txt");	for(int i=1; i<=n; i++)		for(int j=1; j<=n; j++)		{			if(file.eof())				break;			file >> cost[i][j];		}	AllPaths(cost, A, n);	PrintAllPath(n);		return 0;}
      
     
    
   

0 3 8 2147483647 -42147483647 0 2147483647 1 72147483647 4 0 2147483647 21474836472 2147483647 -5 0 21474836472147483647 2147483647 2147483647 6 0

转载地址：http://gxnbb.baihongyu.com/