You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
# include <iostream>
using namespace std ;
# define n 4
int main ( )
{
int i , j , k , l ;
int S [ n ] ; //用于存储已访问过的城市
int D [ n ] [ n ] ; //用于存储两个城市之间的距离
int sum = 0 ; //用于记算已访问过的城市的最小路径长度
int Dtemp ; //保证Dtemp比任意两个城市之间的距离都大( 其实在算法描述中更准确的应为无穷大)
int flag ; ////最为访问的标志, 若被访问过则为1, 从未被访问过则为0
/*初始化*/
i = 1 ; //i是至今已访问过的城市
S [ 0 ] = 0 ;
D [ 0 ] [ 1 ] = 2 ; D [ 0 ] [ 2 ] = 6 ; D [ 0 ] [ 3 ] = 5 ; D [ 1 ] [ 0 ] = 2 ; D [ 1 ] [ 2 ] = 4 ;
D [ 1 ] [ 3 ] = 4 ; D [ 2 ] [ 0 ] = 6 ; D [ 2 ] [ 1 ] = 4 ; D [ 2 ] [ 3 ] = 2 ; D [ 3 ] [ 0 ] = 5 ;
D [ 3 ] [ 1 ] = 4 ; D [ 3 ] [ 2 ] = 2 ;
do {
k = 1 ; Dtemp = 10000 ;
do {
l = 0 ; flag = 0 ;
do {
if ( S [ l ] = = k ) { //判断该城市是否已被访问过,若被访问过,
flag = 1 ; //则flag为1
break ; //跳出循环,不参与距离的比较
} else
l + + ;
} while ( l < i ) ;
if ( flag = = 0 & & D [ k ] [ S [ i - 1 ] ] < Dtemp ) { /*D[k][S[i - 1]]表示当前未被访问的城市k与上一个已访问过的城市i-1之间的距离*/
j = k ; //j用于存储已访问过的城市k
Dtemp = D [ k ] [ S [ i - 1 ] ] ; //Dtemp用于暂时存储当前最小路径的值
}
k + + ;
} while ( k < n ) ;
S [ i ] = j ; //将已访问过的城市j存入到S[i]中
i + + ;
sum + = Dtemp ; //求出各城市之间的最短距离,注意:在结束循环时,该旅行商尚未回到原出发的城市
} while ( i < n ) ;
sum + = D [ 0 ] [ j ] ; //D[0][j]为旅行商所在的最后一个城市与原出发的城市之间的距离
for ( j = 0 ; j < n ; j + + ) { //输出经过的城市的路径
cout < < j < < " " ;
}
cout < < " \n " < < sum ; //求出最短路径的值
}