貪心法———TSP問題

#include<stdio.h>
#define INF 999
using namespace std;

const int n=5;

int TSP(int arc[n][n], int w)   //從頂點w出發
{
    int edgeCount=0, TSPLength=0;
    int min,u,v;
    int flag[n]={0};   //頂點均未加入哈密頓回路
    u=w;
    flag[w]=1;   //将點w加入哈密頓回路
    while(edgeCount<n-1)   //循環直到邊數等于n-1
    {
        min=100;
        for(int j=0; j<n; j++)
        {
            if( (flag[j]==0) && (arc[u][j]!=0) && (arc[u][j]<min) )
            {
                v=j;
                min=arc[u][j];       
            }
        }
		TSPLength+=arc[u][v];
        flag[v]=1;   //将頂點加入哈密頓回路
        edgeCount++;
        printf("%d-->%d\n",u+1,v+1);
        u=v;   //下一次從頂點v出發
    }
    printf("%d-->%d\n",v+1,w+1);   //輸出最後的回邊
    return (TSPLength+arc[u][w]);
}
    
int main(void)
{
    int arc[n][n];
    arc[0][0]=INF; arc[0][1]=3;   arc[0][2]=3;   arc[0][3]=2;   arc[0][4]=6;
    arc[1][0]=3;   arc[1][1]=INF; arc[1][2]=7;   arc[1][3]=3;   arc[1][4]=2;
    arc[2][0]=3;   arc[2][1]=7;   arc[2][2]=INF; arc[2][3]=2;   arc[2][4]=5;
    arc[3][0]=2;   arc[3][1]=3;   arc[3][2]=2;   arc[3][3]=INF; arc[3][4]=3;
    arc[4][0]=6;   arc[4][1]=2;   arc[4][2]=5;   arc[4][3]=3;   arc[4][4]=INF;
    int w=0;
    int s=0;
    s=TSP(arc,0);
    printf("用貪心算法求得的最短路徑是：%d",s);
    return 0;
}