g2.cpp

多段图的分析算法,找到最优路径,用VC编的

#include<stdio.h>

/*typerdefine struct k1()
{
   int a[1];
   k1 *next; 
}
typedefine struct k2()
{
	int

}*/
//int a[13]={0,1,2,3,4,5,6,7,8,9,10,11,12};
int d[13];
int c[12][13];
int cost[13];


int v1[2]={0,1};
int v2[5]={0,2,3,4,5};
int v3[4]={0,6,7,8};
int v4[4]={0,9,10,11};
int v5[2]={12}; 

int sr(int k2[],int k3[],int n1,int n2)
{
	int i,j,min;
//	int min[10];
	//int cost;
	for( i=1;i<=n1;i++)
	{  
		for(j=1;j<=n2;j++)
		{
			if(c[k2[i]][k3[j]]!=0)
	        min=c[k2[i]][k3[j]]+cost[k3[j]];
			

		}	
		for(j=1;j<=n2;j++)
		{  
			if (((c[k2[i]][k3[j]])!=0)&&(c[k2[i]][k3[j]]+cost[k3[j]])<=min)
			{  
		 	  min=c[k2[i]][k3[j]]+cost[k3[j]];
		      d[k2[i]]=k3[j];
			  cost[k2[i]]=min; 
			  //printf("%d \n",k3[j]);
			}
		}
	   printf("%d %d %d \n",k2[i],d[k2[i]],cost[k2[i]] );
	}


   return 0;


}
void main()
{   
	int i;
	int p[6];
	cost[12]=0;
	

	c[1][2]=9;
	c[1][3]=7;
	c[1][4]=3;
	c[1][5]=2;
	c[2][6]=4;
	c[2][7]=2;
	c[2][8]=1;
	c[3][6]=2;
	c[3][7]=7;
	c[4][8]=11;
	c[5][7]=11;
	c[5][8]=8;
	c[6][9]=6;
    c[6][10]=5;
    c[7][9]=4;
    c[7][10]=3;
	c[8][10]=5;
	c[8][11]=6;
	c[9][12]=4;
	c[10][12]=2;
	c[11][12]=5;
	d[9]=d[10]=d[11]=12;
	sr(v4,v5,3,1);
	printf("\n");
	sr(v3,v4,3,3);
	printf("\n");
	sr(v2,v3,4,3);
	printf("\n");
	sr(v1,v2,1,4);
	printf("\n");

	printf("最优解为:\n");
	p[1]=1,p[5]=12;
	for(i=2;i<=4;i++)
	{
		p[i]=d[p[i-1]];
	}
for(i=1;i<=5;i++)
printf(" %d ",p[i]);
printf("\n");
}