最佳路径.cpp

在知道点的坐标或者数量和权重值时

#include<stdio.h>
#include<iostream.h>
#include<math.h>
//-------------------------------
//--------两个数的最小值--------
int min2(int x,int y)
{
	int c;
	if(y!=x)
	c=x<y?x:y;
	else
		c=y;
	return c;
}
//--------------------------------
//-----------第X次标定项的值----------
int min(int x,int r1,int r2,int r3,int r4,int r5,int r6,int r7,int r8)
{
	int r,s,t,c[8]={r1,r2,r3,r4,r5,r6,r7,r8};
		for(s=0;s<7;s++)
		{
	    	for(r=7;r>s;r--)
			{
    	    	if(c[r]<c[r-1])
				{                                                                                                                                                                                                                                                                                                                                                                                                                                                                       
		    		t=c[r];
		    		c[r]=c[r-1];
	    			c[r-1]=t;
				}
			}
		}
	return c[x-1];
}
//-----------------------------------
//--------第X次标定项的列号--------------
int minliehao(int x,int r1,int r2,int r3,int r4,int r5,int r6,int r7,int r8)
{
	int r,s,t,c[8]={r1,r2,r3,r4,r5,r6,r7,r8},d[8]={r1,r2,r3,r4,r5,r6,r7,r8};
		for(s=0;s<7;s++)
		{
	    	for(r=7;r>s;r--)
			{
    	    	if(c[r]<c[r-1])
				{                                                                                                                                                                                                                                                                                                                                                                                                                                                                       
		    		t=c[r];
		    		c[r]=c[r-1];
	    			c[r-1]=t;
				}
			}
		}
		for(r=0;r<8;r++)
			if(d[r]==c[x-1])
			{
				return r+1;
				break;
			}
}



int lujing(int k,int j,int e[8][8])
{
	int e1[1],i;
	for(i=7;i>0;i--)
		if(e[i-1][j-1]!=e[i][j-1])
		{
			e1[0]=minliehao(i,e[i-1][0],e[i-1][1],e[i-1][2],e[i-1][3],e[i-1][4],e[i-1][5],e[i-1][6],e[i-1][7]);
		}
		return e1[0];

//		for(m=1;m<j-k+1;m++)
//			e1[m]=lujing(k,e1[m-1],e[8][8]);
//		for(m=0;m<j-k+1;m++)
//			printf("%5d",e1[m]);
}



//
void main()
{
	int n=100;
	int a[8][8]={{0,1,2,n,n,n,n,n},{1,0,3,3,3,n,n,n},{2,3,0,2,n,n,n,4},{n,3,2,0,2,3,n,3},{n,3,n,2,0,2,n,n},{n,n,n,3,3,0,1,n},{n,n,n,n,n,1,0,1},{n,n,4,3,n,n,1,0}};
//---------------------------
	printf("         ");
	for(int i=1;i<9;i++)
	{
		printf("v%-8d",i);
	}
	printf("\n");
	for(int j=0;j<8;j++)//
	{
			printf("v%-8d",j+1);
			for(int k=0;k<8;k++)//
			{
		    	printf("%-9d",a[j][k]);
			}
			printf("\n");
	}
		printf("\n\n\n\n\n");

//-----------------------------------

		printf("            ");
    	for(i=1;i<9;i++)//
		{
    		printf("v%-8d",i);
		}
//-----------------------------------
    	printf("\n标定起点    0  ");
		int b[8][8]={0,n,n,n,n,n,n,n};
		for(i=1;i<8;i++)
		{
			printf("    (%d)",b[0][i]);
		}
			printf("\n");
		for(i=1;i<8;i++)
		{
			int k;
			k=minliehao(i,b[i-1][0],b[i-1][1],b[i-1][2],b[i-1][3],b[i-1][4],b[i-1][5],b[i-1][6],b[i-1][7]);
			if(minliehao(i,b[i-1][0],b[i-1][1],b[i-1][2],b[i-1][3],b[i-1][4],b[i-1][5],b[i-1][6],b[i-1][7])==minliehao(i-1,b[i-2][0],b[i-2][1],b[i-2][2],b[i-2][3],b[i-2][4],b[i-2][5],b[i-2][6],b[i-2][7]))
				k=k+1;

			printf("标定v%d",k);
			for(j=0;j<8;j++)
			{
				b[i][j]=min2(b[i-1][j],(a[j][minliehao(i,b[i-1][0],b[i-1][1],b[i-1][2],b[i-1][3],b[i-1][4],b[i-1][5],b[i-1][6],b[i-1][7])-1]+min(i,b[i-1][0],b[i-1][1],b[i-1][2],b[i-1][3],b[i-1][4],b[i-1][5],b[i-1][6],b[i-1][7])));
				printf("    (%3d)",b[i][j]);
			}
			printf("\n");
		}
		printf("\n\n\n\n");
		
		int k[7],x,y;
		scanf("%d%d",&x,&y);
		k[0]=lujing(x,y,b);
		int m1=0;
		for(int m=1;m<y-x+1;m++)
		{
			
			if(k[m-1]==1)
				break;
			else
			{
		    	k[m]=lujing(x,k[m-1],b);
		    	m1=m1+1;
			}
		}
		
		for(m=m1;m>=0;m--)
			printf("%d-->",k[m]);
		printf("%d",y);
}