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

《计算机算法(C++版)》5.2.

用前向算法和后向算法进行动态规划，前向算法从后往前递推；后向算法，从前往后递推。

C++代码如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;class Graph{private:	const static int MAXSIZE = 101;	int VertexNum;	int c[MAXSIZE][MAXSIZE];	struct node	{		int vertex;		struct node *link;	};	struct node** headnodes;	void DestroyHeadnodeChain(node * head)	{		node * Ptr = head;		if(head == NULL)			return;		while(Ptr != NULL)		{			Ptr = head->link;			head->link = NULL;			delete head;			head = Ptr;		}	}public:	Graph(int n): VertexNum(n)	{		headnodes = new node*[VertexNum+1];		for(int i=1; i<=VertexNum; i++)			headnodes[i] = NULL;	}	void ReadEdge(int i, int j, int w)	{		if(headnodes[i] == NULL)		{			headnodes[i] = new node;			headnodes[i]->vertex = j;			headnodes[i]->link = NULL;		}		else		{			node * Ptr = headnodes[i];			while(Ptr->link != NULL)			{				Ptr = Ptr->link;			}			Ptr->link = new node;			Ptr = Ptr->link;			Ptr->vertex = j;			Ptr->link = NULL;		}		c[i][j] = w;	}	void ReadAdverseEdge(int i, int j, int w)	{		if(headnodes[j] == NULL)		{			headnodes[j] = new node;			headnodes[j]->vertex = i;			headnodes[j]->link = NULL;		}		else		{			node * Ptr = headnodes[j];			while(Ptr->link != NULL)			{				Ptr = Ptr->link;			}			Ptr->link = new node;			Ptr = Ptr->link;			Ptr->vertex = i;			Ptr->link = NULL;		}		c[i][j] = w;	}	void PrintEdge()	{		node *Ptr;		cout << "Graph Edge: " << endl;		for(int i=1; i<=VertexNum; i++)		{			Ptr = headnodes[i];			if(Ptr == NULL)				cout << "Vertex " << i << " has no going edge.";			while(Ptr != NULL)			{				cout << '<' << i << ','  << Ptr->vertex << '>';				Ptr = Ptr->link;			}			cout << endl;		}	}	void InitWeight()	{		for(int i=0; i<=VertexNum; i++)			for(int j=0; j<=VertexNum; j++)			{				if(i == j)					c[i][j] = 0;				else					c[i][j] = numeric_limits
      
       ::max();			}	}	void PrintWeight()	{		cout << "Graph Edge Weight: " << endl;		for(int i=1; i<=VertexNum; i++)		{			for(int j=1; j<=VertexNum; j++)				if(c[i][j] != numeric_limits
       
        ::max())					cout << c[i][j] << ' ';				else					cout << "INF" << ' ';			cout << '\n';		} 	}	// 前向方法	int FGraph(int k, int n, int p[])	{		double cost[MAXSIZE];		int    d[MAXSIZE];		int    r;		cost[n] = 0;		for(int j=n-1; j>=1; j--)		{			r = FindOptNextVertex(j, cost);			//cout << r << endl;			cost[j] = cost[r] + c[j][r];			d[j] = r;		}		// 寻找最小费用路径		p[1] = 1;		p[k] = n;		for(int j=2; j<=k-1; j++)			p[j] = d[p[j-1]];		return cost[1];	}	int FindOptNextVertex(int j, double cost[])	{		int r = 0;		int Min = numeric_limits
        
         ::max(); node* Ptr = headnodes[j]; while(Ptr != NULL) { if(cost[Ptr->vertex] + c[j][Ptr->vertex] < Min) { Min = cost[Ptr->vertex] + c[j][Ptr->vertex]; r = Ptr->vertex; } Ptr = Ptr->link; } return r; } // 后向方法 int BGraph(int k, int n, int p[]) { double bcost[MAXSIZE]; int d[MAXSIZE]; int r; bcost[1] = 0; for(int j=2; j<=n; j++) { r = FindOptPrevVertex(j, bcost); bcost[j] = bcost[r] + c[r][j]; d[j] = r; } // 寻找最小费用路径 p[1] = 1; p[k] = n; for(int j=k-1; j>=2; j--) p[j] = d[p[j+1]]; return bcost[n]; } int FindOptPrevVertex(int j, double cost[]) { int r = 0; int Min = numeric_limits
         
          ::max(); node* Ptr = headnodes[j]; while(Ptr != NULL) { if(cost[Ptr->vertex] + c[Ptr->vertex][j] < Min) { Min = cost[Ptr->vertex] + c[Ptr->vertex][j]; r = Ptr->vertex; } Ptr = Ptr->link; } return r; } int PrintMinimumCostPath(int k, int p[]) { cout << "Minimum Cost Path: "; for(int i=1; i
          
           "; cout << p[k] << endl; } ~Graph() { for(int i=0; i<=VertexNum; i++) { if(headnodes[i] != NULL) DestroyHeadnodeChain(headnodes[i]); } }};int main(){ int i, j, w; int k = 5; int p[5] = {0}; Graph g(12); g.InitWeight(); ifstream edge("edge.txt"); while(!edge.eof()) { edge >> i >> j >> w; g.ReadEdge(i, j, w); } //g.PrintEdge(); cout << "Forward Method." << endl; cout << "Minimum Cost: " << g.FGraph(k, 12, p) << endl; g.PrintMinimumCostPath(k, p); cout << endl; edge.seekg(0, ios::beg); while(!edge.eof()) { edge >> i >> j >> w; g.ReadAdverseEdge(i, j, w); } //g.PrintEdge(); edge.close(); cout << "Backward Method." << endl; cout << "Minimum Cost: " << g.BGraph(k, 12, p) << endl; g.PrintMinimumCostPath(k, p); return 0;}
          
         
        
       
      
     
    
   

1 2 91 3 71 4 31 5 22 6 42 7 22 8 13 6 23 7 74 8 115 7 115 8 86 9 66 10 57 9 47 10 38 10 58 11 69 12 410 12 211 12 5

如果不用临接表和逆临接表表示，那么可以直接通过矩阵表示递推。

FindOptNextVertex方法：

int FindOptNextVertex1(int j, double cost[])	{		int r = 0;		int Min = numeric_limits
   
    ::max();				for(int k=1; k<=VertexNum; k++)		{			if(k!=j && c[j][k] != numeric_limits
    
     ::max())			{				//cout << "Cost[" << k << "]: " << cost[k] << ", c[" << j << "][" << k << "]:" << c[j][k] << endl;				if(c[j][k] + cost[k] < Min)				{					Min = c[j][k] + cost[k];					r = k;				}			}		}		//cout << "j = " << j << ", r = " << r << endl;		return r;	}
    
   

FindOptPrevVertex方法：

int FindOptPrevVertex1(int j, double bcost[])	{		int r = 0;		int Min = numeric_limits
   
    ::max();				for(int k=1; k<=VertexNum; k++)		{			if(k!=j && c[k][j] != numeric_limits
    
     ::max())			{				// cout << "BCost[" << k << "]: " << bcost[k] << ", c[" << k << "][" << j << "]:" << c[k][j] << endl;				if(c[k][j] + bcost[k] < Min)				{					Min = c[k][j] + bcost[k];					r = k;				}			}		}		//cout << "j = " << j << ", r = " << r << endl;		return r;	}
    
   

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