[求助]如何求出遍历所有城市的最短路径

各位大大:如果有一幅路线图,上面有N个城市,并且有这N个城市之间的交通路费(一个城市至少有一个连接路线),如果去旅游,要把这所有城市都游玩一遍,问怎样才能用最少的钱把这N个城市走完(一个城市可以走2次或以上,即是个无向图)我想了好久~~拜托各位大大了

我的最小生成树丫!!!!!!!!!!!!!!!!!!!

可以详细点吗~我们老师给了个类似拓扑排序的算法~想知道有没类似的算法~谢谢

[QUOTE]

我的最小生成树丫!!!!!!!!!!!!!!!!!!!

[/QUOTE]
你太有才了~~~~

楼主的问题看似有点问题。
既然规定好费用要最低，且每个城市至少经过一次，怎么可能会允许城市经过2次或2次以上呢？那1次以上的开销不是白白浪费了嘛。


这个问题叫旅行商问题（Traveling Salesman Problem, TSP），是一个典型的NP难问题，没有一个能给出问题精确解的多项式算法。
你们老师如果说给一个拓扑排序算法，那肯定只能用于几个城市的小规模TSP问题，一般中等规模以上的TSP问题多用智能优化算法（如GA、ACO等）在有限时间内给出近似解。

PS：一般的对称TSP问题一般默认图形是强连通图

好深奥

支持用最小生成树...

不用说，先定义一个图，然后画出每几个城市的顶点。加上权值，然后按最小生成树，

最小生成树只能应用于小规模问题，且所得不一定是精确解。