mindis.cpp

n个顶点构成的完全图

// MinDis.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include "def.h"

/*从顶点1出发的最短哈密顿回路*/
int main(int argc, char* argv[])
{
	int Sum = MAX;		/*Sum saves the length of the shortest path*/
	int S   = 0;		/*S saves the current values of the path length*/						   
	int passed[N+1];	/*Array passed mark visited nodes,visited set 1 or set 0*/
	int p[N+1];			/*Array p,N represent steps in the path,Its value represents the node in current step*/
	int path[N+2];		/*Array path save the shortest path*/
	int i,j,l=0;
	int d[N+1][N+1];

	for (i=1; i<=N; i++)
	{
		passed[i] = 0;
	}

	for (i=1; i<=N; i++)
	{
		for (j=1; j<i; j++)
		{
			d[i][j] = rand()%100+1;/*generate random numbers between 1 and 100 as the distance value */
			d[j][i] = d[i][j];
			printf("d[%d][%d]=%d\t",i,j,d[i][j]);
		}
	}

	l++;
	p[1]=1;
	passed[1]=1;

L0: l++;
	j=0;

L1: j++;
	if (j>N)
		goto L2;

	if (passed[j])
		goto L1;

	p[l]=j;
	if ((S+=d[p[l-1]][j]) >= Sum)
	{
		S-=d[p[l-1]][j];
		goto L1;
	}

	passed[j]=1;

	if (l<N)
		goto L0;

	if ((S+d[p[N]][p[1]]) < Sum)
	{
		Sum = S+d[p[N]][p[1]];
		for (i=1; i<=N; i++)
		{
			path[i] = p[i];
		}
	}
	l++;

L2: l--;
	if(l>1)
	{
		j=p[l];
		S-=d[p[l-1]][j];
		passed[j] = 0;
		goto L1;
	}
	else
	{
		printf("the shortest path is:\t");
		for (i=1; i<=N; i++)
		{
			printf("%d\t",path[i]);
		}
		printf("\nthe shortest length is: %d\n",Sum);
	}

	return 0;
}