最短経路問題ダイナミック企画

問題の参考：  
http://iprai.hust.edu.cn/icl2002/algorithm/algorithm/technique/dynamic_programming/introduction.httm葃example 1
       地図があります。各結点は都市を表しています。二つの結点間の路線は道路を表しています。オンラインの数字は都市間の距離を表しています。図1に示すように、結点Aから結点Eまでの最短距離を探してみます。
     
深度優先検索法でこの問題を解決できます。再帰式は次の通りです。
ここではvに隣接するノードの集合であり、w（v，u）はvからuまでの辺の長さを示す。
このプログラムの効率はどうですか？訪問した都市以外の都市は毎回訪問するので、時間の複雑さはO（n！）であり、これは「指数級」のアルゴリズムであることが分かります。
     
まず、このアルゴリズムを観察します。B 1からEまでの最短距離を求める場合、まずC 2からEまでの最短距離を求める。B 2からEまでの最短距離を求めて、C 2からEまでの最短距離を求めました。つまり、C 2からEまでの最短距離を二回求めました。C 1、C 2からEまでの最短距離を求める過程で、D 1からEまでの最短距離も2回求められていることが分かります。全体のプログラムの中で、D 1からEまでの最短距離は4回求められました。解を求める過程において、同時に求められる最短距離が「記録されている」場合は、随時呼び出して、このような状況を回避することができる。そこで、このアルゴリズムを改善して、毎回求めたvからEまでの最短距離を記録して、アルゴリズムの中で再帰的にMinDistance（v）を求めた時に、以前にMinDistance（v）が求められたかどうかを先にチェックして、もし求めたらもう一度求めなくてもいいです。以前の記録を検索すればいいです。このように、すべての点はn個あるので、異なる状態数はn個あり、このアルゴリズムの数はO（n）である。
さらに、この再帰的な呼び出しのオーバヘッドを低減することができるように、この再帰的な再帰的なプッシュに変更することができる。
コードは以下の通りです

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("in.txt");
#define maxLength 20

int matrix[maxLength][maxLength];   //       
int minPath[maxLength];             //               
int trace[maxLength];               //       
int v_n; //    

int MinDistance(int v)
{
	if(minPath[v]>0) return minPath[v]; 
	if(v==v_n-1) return 0;     //   
	int min=1000,t,j;
	for(int i=v+1;i<v_n;i++)
	{
		if(matrix[v][i]>0) 
		{	
			t = matrix[v][i]+MinDistance(i);
			if(min>t){ min=t; j=i;}
		}
	}
	minPath[v]=min;
	trace[v]=j;
	return minPath[v];
}

int main()
{
	
	fin>>v_n;
	for(int i=0;i<v_n;i++)
	{
		for(int j=0;j<v_n;j++)
		{
			fin>>matrix[i][j];
			cout<<matrix[i][j]<<"-";
		}
		cout<<endl;
	}
	memset(minPath,0,sizeof(int)*maxLength);
	memset(trace,0,sizeof(int)*maxLength);
	int minD = MinDistance(0);
	cout<<"    ："<<minD<<endl;
	i=0;
	cout<<"1-->";
	while(minD>0)
	{
		cout<<trace[i]+1<<"-->";
		minD = minD-matrix[i][trace[i]];
		i = trace[i];
	}
	cout<<endl;
	return 0;
}

   入力ファイル：in.txt 
（例は「アルゴリズム設計と分析」（夏紅霞編集長）教材147ページの例題から来ています。
12 0 9 7 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力ファイル:
0-0-0-0-0-0-0-0-0-0 0-0 0 0-0 0 0-0 0 0-0 0 0-0 0-0 0 0-0 0-0 0-0 0-0 0 0-0-0 0-0 0 0-0 0 0-0 0 0 0 0-0 0 0-0 0 0-0 0-0-0 0 0 0-0 0 0 0-0-0-0 0-0 0 0 0 0 0-0 0 0 0 0-0 0 0 0-0 0 0 0 0-0-0 0 0 0 0 0 0-0 0 0 0 0-0 0 0-0 0 0-0-0 0 0 0-0 0-0-0-0-0-0-0-0-0-0 0 0 0 0 0 0 0-0-0-0-0-0-0 0-0-0-0-最短経路：16 1-->2-->7-->10-->12-->Pressany key to continue