ddt.cpp

算法设计于分析中的多段图问题

#include <iostream.h>
#include <malloc.h>
#include <conio.h>

void main()
{   int num=1;
	int nodes,edges,i,j,r,k;
	int *D,*cost,*P;/*D是动态数组，COST数组存放代价，P数组是最小成本路径*/
	typedef int  **Value;
	Value value;
   	cout<<"                           开始演示程序"<<endl;	 
	cout<<"请输入结点数目:";cout<<endl<<"nodes=";/*输入图的结点数*/
	 cin>>nodes;
	 cout<<"请输入边的数目:";cout<<endl<<"edges=";/*输入图的边数*/
	cin>>edges;
	D=(int*)malloc(nodes*sizeof(int));
	cost=(int*)malloc(nodes*sizeof(int));
	P=(int*)malloc(nodes*sizeof(int));
	value=(Value)malloc(nodes*sizeof(int*));
	for(i=0;i<nodes;i++)
	{
		value[i]=(int*)malloc(nodes*sizeof(int));
	}

	for(i=0;i<nodes;i++)
	 for(j=0;j<nodes;j++)
		 value[i][j]=-1;

	for(i=1;i<=edges;i++,num++)
	{
		cout<<"edge"<<num<<":"<<"from";/*输入图的路径*/
		cin>>j;
		cout<<"to:";
		cin>>k;
		cout<<"value=";
		cin>>value[j][k];
	}
     cost[nodes]=0;

	for(j=nodes-1;j>=1;j--)
	{
	 for(r=j+1;value[j][r]<0&&r<=nodes;r++);
       D[j]=r;
        k=value[j][r]+cost[r];
        
	for(;r<=nodes;r++)
		if(value[j][r]>0)      
			if(value[j][r]+cost[r]<k)
			 {
				 k=cost[j]=value[j][r]+cost[r];
				 D[j]=r;
			} 
	}

	P[1]=1;
	for(j=2;P[j-1]<nodes;j++)
	 {
		 k=P[j-1];
		 P[j]=D[k];
	}
	 cout<<endl<<"最小成本路径:"<<endl;/*输出最小成本路径*/
	 for(i=1;i<=j-1;i++)
		 cout<<P[i]<<"->";
	  char ch=getch();
}