short.cpp

算法分析和设计 最短路径问题 计算一个点到其他各个点的最短路径

#include "iostream"

using namespace std;
#define STACK_MAX 100;


const int CX[4][4] = {{1,3,2,3},{2,2,1,4},{2,3,4,5},{2,3,1,2}};
const	int CY[5][3] ={{3,3,2},{2,4,1},{1,1,2},{2,2,2},{4,3,3}};
void main()
{

int i;
int j;

//	BOOL  path[][]
	int C[5][4];


	for( i=0;i<5;i++)
		for( j = 0;j<4;j++)
		{
			C[i][j] = 0;
		}
		
		//
	for( i =1;i<5;i++)
	{
	  C[i][0] = C[i-1][0]+CX[0][i-1];
	
	}


	for(i=1;i<4;i++)
	{
		 C[0][i] = C[0][i-1]+CY[0][i-1];
	}
	

/*	for(i=0;i<5;i++)
	{
		// C[0][i] = C[0][i-1]+CX[0][i-1];
	cout<<C[i][0]<<"  ";
	}

	cout<<endl;

	for(i=0;i<4;i++)
	{
		// C[0][i] = C[0][i-1]+CX[0][i-1];
		cout<<C[0][i]<<"  ";
	}*/
//	for()

	//计算最短路径长度。
	for(i =1;i<5;i++)
	{
		for( j =1;j<4;j++)
		{
			int temp1 = C[i-1][j] +CX[j][i-1];
			int temp2 = C[i][j-1] +CY[i][j-1];
			if(temp1<temp2)
				 C[i][j] = temp1;
			else C[i][j] = temp2;
		}
	}

	for(i =0;i<5;i++)
	{
		for( j =0;j<4;j++)

		{
			cout<<"  "<< C[i][j];
		}
		cout<<endl;
	}

	//求指出最短路径
	//1表示向右，0表示向上。
	int stack[100];
	int top=-1;
	j =3;
	for(i =4;i>=1;)
	{
		for( ;j>=1;)
		{
				top++;
			if(C[i][j]-C[i-1][j]==CX[j][i-1])
			{
				stack[top] = 1;
				i--;
			//	cout<<stack[top]<<"     ";
				break;
			}
			
			else 
			{
				stack[top] = 0;
				j = j-1;
		//		cout<<stack[top]<<"     ";
				break;
			}

		}
		if(j==0||i==0)
			break;
	}

	while(i!=0)
	{
		top++;
		stack[top] = 1;
		i--;
	}
		
	while(j!=0)
	{
		top++;
		stack[top] = 0;
		i--;
	}
	cout<<"最短路径是："<<endl;
	for( i = top;i>=0;i--)
	{
		cout<<stack[i]<<"  ";
	}
}