알고리즘 설계와 분석: 제4장 동적 기획 4.3 다단도의 가장 짧은 경로 문제

/*
          :
  ：        G(V,E,W)，       V   
k       V i ，1≤i ≤k，k≥2，  E       
(u,v)，  uЄ V i， v ∈ V i+m  ，m≥1，          。

       :     k-1          t        。       
  ，            。   cost[i]    i    t     ，   path[i]
    i    t               

      :     k-2         t        。  ，              
  ，            cost path      ，    ，        s   t      
  。
  s path           

  :
1 cost[i]    i   t     
2      :cost[i] =  min{c[i][j] + cost[j]},1<= j <= n ,  j != i 
 path[i] = j,j   c[i][j] + cost[j]   j
3     :cost[n-1] = 0
4     :cost[0]

    :
 route[n]     s      t           
1）    i,0<=i<n, cost[i]       ，path[i]    -1,cost[n-1]    0
2） i = n - 2;
3)          cost[i] path[i]
4) i = i -1 ; i > = 0,   (3),      (5)
5) i = 0 ,route[i] = 0
6) route[i] = n-1,    ，     (7)
7)i = i + 1,route[i] = path[route[i-1]，   (6)

    :
  :    ，   0  
   :      :                

  :
10(    ) 19（    ）
0 1 4
0 2 1
0 3 3

1 4 9
1 5 8
2 3 1
2 4 6
2 5 7
2 6 8
3 5 4
3 6 7

4 7 5
4 8 6
5 7 8
5 8 6
6 7 6
6 8 5

7 9 7
8 9 3

  :
15
0 2 3 5 8 9
*/

/*
  :
1        	//    ，  n-1 ，  ，           ，    ：  
	for(int i = n-2 ; i >= 0 ; i--)
	{
		//        
		int iMin = MAX;
		for(int j = i+1 ; j <= n-1 ; j++)
		{
			//  
			if(g_iCost[j] != MAX && g_iMatrix[i][j] != -1)
			{
				iRet = g_iCost[j] + g_iMatrix[i][j];
				if(iMin > iRet)
				{
					iMin = iRet;
					g_iCost[i] = iMin;
					//        
					g_iPath[i] = j;

2     ，  
	//     ,     
	if(g_iCost[iEnd] != MAX)
	{
		return g_iCost[iEnd];
	}
	//          
	int iMin = MAX;
	int iRet;
	for(int i = 0 ; i <= n-1 ; i++)
	{
		//       ,  ,cost[i] = min { cost[j] + c[i][j])
		if(i > iEnd && g_iMatrix[iEnd][i] != -1)
		{
			iRet = dp(i,n) + g_iMatrix[iEnd][i];
			if(iMin > iRet)
			{
				iMin = iRet;

3  path[i] = j;j  cost[i]      j
//        
g_iPath[i] = j;

4 1 cost[i]    i   t     
2      :cost[i] =  min{c[i][j] + cost[j]},1<= j <= n ,  j != i 
 path[i] = j,j   c[i][j] + cost[j]   j
*/

#include <iostream>
#include <string.h>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

const int MAXSIZE = 100;
int g_iMatrix[MAXSIZE][MAXSIZE];
int g_iCost[MAXSIZE];
int g_iPath[MAXSIZE];
int g_iRoute[MAXSIZE];

const int MAX = 1000000000;

int max(int a,int b)
{
	return a > b ?  a : b;
}

//        
int dp2(int n)
{
	//          

	int iRet;
	int iCnt = 0;
	//    ，  n-1 ，  ，           ，    ：  
	for(int i = n-2 ; i >= 0 ; i--)
	{
		//        
		int iMin = MAX;
		for(int j = i+1 ; j <= n-1 ; j++)
		{
			//  
			if(g_iCost[j] != MAX && g_iMatrix[i][j] != -1)
			{
				iRet = g_iCost[j] + g_iMatrix[i][j];
				if(iMin > iRet)
				{
					iMin = iRet;
					g_iCost[i] = iMin;
					//        
					g_iPath[i] = j;
				}
			}
		}
	}
	return g_iCost[0];
}

//        ，      
int dp(int iEnd,int n)
{
	//     ,     
	if(g_iCost[iEnd] != MAX)
	{
		return g_iCost[iEnd];
	}
	//          
	int iMin = MAX;
	int iRet;
	for(int i = 0 ; i <= n-1 ; i++)
	{
		//       ,  ,cost[i] = min { cost[j] + c[i][j])
		if(i > iEnd && g_iMatrix[iEnd][i] != -1)
		{
			iRet = dp(i,n) + g_iMatrix[iEnd][i];
			if(iMin > iRet)
			{
				iMin = iRet;
			}
		}
	}
	return g_iCost[iEnd] = iMin;
}

/*        */
bool readData(const string& sFileName)
{
	if(sFileName.empty())
	{
		return false;
	}
	ifstream infile;
	infile.open(sFileName,ios::in);
	if(infile.bad())
	{
		cout << "    :" << sFileName << ",    " << endl;
		return false;
	}
	string sLine;
	vector<string> vecTemp;
	int iBeg,iEnd,iWeight;
	string sBeg,sEnd,sWeight;
	while(getline(infile,sLine))
	{
		//if(boost::starts_with(sLine,"***") ||  sLine.empty())
		if(string::npos != sLine.find("*") || sLine.empty())
		{
			continue;
		}
		else
		{
			vecTemp.clear();
			int iFirstBlank = sLine.find_first_of(" ");
			int iLastBlank = sLine.find_last_of(" ");
			int iLen = iLastBlank - iFirstBlank - 1;
			sBeg = sLine.substr(0,iFirstBlank);
			sEnd = sLine.substr(iFirstBlank + 1, iLen);
			sWeight = sLine.substr(iLastBlank + 1,sLine.size() - iLastBlank - 1);
			vecTemp.push_back(sBeg);
			vecTemp.push_back(sEnd);
			vecTemp.push_back(sWeight);
			if(vecTemp.size() != 3)
			{
				cout << "         ，   " << endl;
				return false;
			}
			else
			{
				iBeg = atoi(vecTemp.at(0).c_str());
				iEnd =	atoi(vecTemp.at(1).c_str());
				iWeight = atoi(vecTemp.at(2).c_str());
				cout << " <" << iBeg << "," << iEnd << ">,  :" << iWeight << endl; 
				//  ，           ，              
				g_iMatrix[iBeg][iEnd] = iWeight;
			}
		}
	}
	return true;
}

/*      ，path[8] = 9,path[6] = 8,path[5] = 6,path[0] = 2,path[1] = 5,g_iPath[],0,2,3,5,8,9， Path[0]  ，*/
void printPath(int n)
{
	for(int i = 0 ; i!= n -1  ; i = g_iPath[i] )
	{
		cout << i << " ";
	}
	cout << n-1 << endl;
}

void process1()
{
	memset(g_iMatrix,-1,sizeof(g_iMatrix));
	readData("./data.txt");
	int iEdgeNum = 19;
	int n = 10;
	//       
	for(int i = 0 ; i <= n - 1 ; i++)
	{
		g_iCost[i] = MAX;
	}
	//             
	g_iCost[n-1] = 0;
	memset(g_iPath,-1,sizeof(g_iPath));
	cout << dp2(10) << endl;
	printPath(n);
}

void process()
{
	int n;
	while(cin >> n)
	{
		int iBeg,iEnd,iDis;
		memset(g_iMatrix,-1,sizeof(g_iMatrix));
		int iEdgeNum ;
		cin >> iEdgeNum;
		for(int k = 0 ; k < iEdgeNum ; k++)
		{
			cin >> iBeg >> iEnd >> iDis;
			g_iMatrix[iBeg][iEnd] = iDis;
		}
		//       
		for(int i = 0 ; i <= n - 1 ; i++)
		{
			g_iCost[i] = MAX;
		}
		//             
		g_iCost[n-1] = 0;
		memset(g_iPath,-1,sizeof(g_iPath));
		dp(0,n);
		cout << g_iCost[0] << endl;
	}
}

int main(int argc,char* argv[])
{
	process1();
	getchar();
	return 0;
}