c语言编写的货郎担算法

c语言编写的货郎担算法，可以运行，大家参考参考

/*文件名：ExamSalesMan.cpp  主工程文件*/
/*
#include “EnumSalesMan.h“
#include “TrackBackSalesMan.h“
#include “BoundSalesMan.h“
int _tmain（int argc _TCHAR* argv[]）

{
     DySalesMan sm;
     sm.PrintMatrix（）;
     sm.Travel（）;
     EnumSalesMan sm2;
     sm2.Travel（）;
     TrackBackSalesMan sm3;
     sm3.Travel（）;
     BoundSalesMan sm4;
     sm4.Travel（）;
     return 0;
}
/* 文件名：SalesMan。H  货郎担基类头文件  */

#pragma once
#include 
#include 
using namespace std;
class SalesMan
{
protected:
     enum{MAXNUM=999}; //最大值设为无穷大

     vector >  matrix; //对应的邻接矩阵
     vector path; //记录走过的最小成本路径

     int minValue;//最小路径长度

public:
     SalesMan（）;
     virtual ~SalesMan（）{matrix.clear（）;path.clear（）;}

     void PrintMatrix（）; //打印矩阵值

     void PrintPath（）;  //打印路径 

     virtual void Travel（）{}; //主要寻找路径的函数，将在子类里面实现
};
/* 文件名：SalesMan。Cpp 货郎担基类源文件  */

//#include “StdAfx.h“
///#include “SalesMan.h“
SalesMan::SalesMan（） //构造函数，从文件中读取数值，生成图的邻接矩阵，

{//认为矩阵结点从0开始
     fstream fin（“in.txt“）;
     if （!fin）
     {    
         cerr<<“file open failed!“<
         return;
     }
     int n;
     fin>>n;
     path.resize（n-1）; //路径记录中间的那些结点
     //从文件里取值
     for （int i=0;i     {
         vector col;       

         for （int j=0;j         {
              int num;

              fin>>num;
              col.push_back（num）;
         }            
         matrix.push_back（col）;
     }
     fin.close（）;
}
void SalesMan::PrintPath（）
{
     cout<<0<<“\t“;
     for （unsigned int i=0;i
         cout<     cout<<“0“<}
void SalesMan::PrintMatrix（）
{
     int n=（int）matrix.size（）;
     for （int i=0;i     {
         for （int j=0;j              cout<
         cout<     }
}
 
/* 文件名：EnumSalesMan.h  枚举法  */

#pragma once
#include “salesman.h“
class EnumSalesMan :
     public SalesMan

{
protected:
     int Cost（vector A）; //获取A中保存的路径的路径长度，被被枚举法调用

     void Enumerate（vector Aint i）; //利用枚举法求最短的那条路径，被被枚举法调用

public:
     void Travel（）;

};
/*  文件名：EnumSalesMan.cpp  枚举法  */

#include “StdAfx.h“
#include “EnumSalesMan.h“
void EnumSalesMan::Travel（）
{
     vector B;     

     B.resize（path.size（））;
     for （unsigned int i=0;i
     {
         B[i]=i+1;
     }
     minValue=Cost（B）;//初始化路径的长度
     Enumerate（B0）;
     //把路径打印出来以及路径长度
     cout<<“Enumerate  minValue:“<     PrintPath（）;
}
int EnumSalesMan::Cost（vector A）

{
     //获取A中保存的路径的路径长度
     int sum=matrix[0][A[0]];//先求从0到第一个点的距离

     for （unsigned int i=1;i
     {
         sum+=matrix[A[i-1]][A[i]];
     }
     sum+=matrix[A[i-1]][0];//再加上最后一个点到0点的距离
     return sum;
}
void EnumSalesMan::Enumerate（vector Aint i）
//利用枚举法求最短的那条路径参数A中保存的路径可能经多的点
{
     if （i==A.s

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      86016  2007-10-24 21:03  货担郎\Debug\vc60.pdb

     文件      14266  2007-10-24 21:03  货担郎\货担郎.cpp

     文件       4221  2007-10-24 21:02  货担郎\货担郎.dsp

     文件        520  2007-10-24 21:02  货担郎\货担郎.dsw

     文件      25600  2007-10-24 23:28  货担郎\货担郎.ncb

     文件          0  2007-10-24 21:03  货担郎\货担郎.plg

     文件      99840  2007-10-24 21:04  货担郎\货郎担.doc

     目录          0  2009-08-06 09:54  货担郎\Debug

     目录          0  2009-08-06 09:54  货担郎

----------- ---------  ---------- -----  ----

               230463                    9