C++旅行商问题(共10页).doc

精选优质文档-倾情为你奉上旅行商问题实验报告学院： 计算机科学与技术 专业：计算机科学与技术学号： 班级： 姓名： （本程序在的环境下实现）一、 问题描述：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或旅费）最小。例如：给定4个城市a，b，c，d及其各城市之间的路程,找出其最短路径ADCB235178二、算法思想：首先是在图为完全图的前提下，构造各城市间的图的结构，采用邻接数组的形式，将各个城市间的距离存储于图的数组中，用一个函数递归寻找从同一个顶点出发的各个城市的所有路径，再求出各个路径的路程，并与相应的路径输出，对路程数组进行冒泡排序后，经比较找出最短路径并输出。三具体实现及分析：图结构的定义：struct MGraph char vexs