加权图最短路径设计C++

Question

我在为C++数据结构课程分配的项目制定计划时遇到了困难。我要求的不是书面代码，而是攻击计划。基本上我很难把这件事想清楚。

如何从这个加权的无向地图构造一个加权图，以便能够找到从一个集合顶点(天使体育场)到以下的最短路径：

1. 所有大联盟体育场
2. 全国联盟体育场
3. 全美国联盟体育场

我还必须允许用户通过选择他们想参观的体育场来规划他们的梦想假期。

该程序只需打印参观体育场的数量和在每种情况下的总行程。

我的第一个想法是为这四个案例中的每一个都制定相应的方法。我甚至不知道该如何去归还参观过的体育场的数量和距离。当您需要返回两个值时，使用结构是否是最佳的？

更不用说最短路径使用哪种算法了。我有一个实现Dijkstra的以前的任务。我班上的其他一些人正在使用最小生成树。

在最短的路径上有一个函数会更有意义，这个函数包含要访问的体育场列表，但我不知道如何构造邻接矩阵。

我正在制作一个输入文件，以读取像这样形成的邻接矩阵(边、权)：

0 1 340
0 2 110

这是这种情况下的最佳结构吗？我不知道如何区分大联盟，全国和美国。是否需要单独的输入文件？还是有更好的组织方式？

如果您感兴趣，以下是完整的作业：[word文件]

Answer 1

您需要实现TSP的不同实例(没有最后一跳)，在根据问题中指定的标准选择的旅游场馆中实现TSP的不同实例。

例如,

1. 设计一个旅行的所有大联盟体育场与最短的路径开始在一个体育场在加利福尼亚州。打印参观的体育场数量和总行程。

minCost = inf

( CaliforniaStadiums体育场)

minCost = min(minCost，TSP (体育场，MLStadiums))

希望这能有所帮助。

鲁德拉