c++ - 查找从起点到目的地的所有可能航班

Question

我最近尝试编写一个函数，该函数输出所有可能的飞行计划，给定起点和终点，不包括任何循环（没有两次访问机场）。我将在下面描述我解决这个问题的基本方法。每个飞行计划都包含一个指向航班的共享指针向量，该航班有一个名称并连接两个机场。机场表示为字符串。我一直在尝试编写的函数具有以下签名

std::vector<std::shared_ptr<FlightPlan>> allFlightPlans(std::string from, std::string to, 
        std::vector<std::string>> airports, std::vector<std::shared_ptr<Flight>> flights,
        std::vector<std::string> visited_airports, 
        std::vector<std::shared_ptr<FlightPlan>> &route);,

其中 Flight 是具有公共操作的类

• std::string getFrom()，获取航班出发的机场，
• std::string getTo(),得到航班去往的机场，
• std::string getName(),获取航班的名称，以及
• 构造函数Flight(std::string from, std::string to, std::string name)，它构造一个 Flight 对象。

请注意，两个航班可能具有相同的名称，但仅在以下情况下：假设航班 1 连接机场 A 和 B，航班 2 连接机场 C 和 D。如果 C 和 D 与 A 和 B 不同，则航班 2 可能具有相同的名称作为航班1。此外，相同的两个机场之间可能有不止一个航班，只要它们的名称不同。

我不确定将函数编写如下是否更容易：

std::vector<std::shared_ptr<FlightPlan>> allFlightPlans(std::string from, std::string to, 
        std::map<std::string, std::vector<std::string>> vertices, std::map<std::string, 
        std::shared_ptr<Flight>> edges, std::vector<std::string> visited_airports,
        std::vector<std::shared_ptr<FlightPlan>> &route);

在第二个版本中，第一个映射中的每个 std::string 代表一个机场，第一个映射中的字符串向量代表相关机场的邻居。同样，对于第二张地图，每个字符串都是一个机场，每个共享航班指针的向量都是从该点开始的航班。

我现在将描述我对函数的第一个版本的方法。我编写此函数的基本算法涉及从 from airport 开始并查找其所有邻居（从该机场开始的航班），如下所示：

std::vector<std::shared_ptr<Flight>> neighbours;
std::for_each(flights.begin(), flights.end(), [](std::shared_ptr<Flight> flight) {
  if (flight->getFrom() == from) neighbours.emplace_back(flight);
});

获得所有邻居后，我调用一个辅助函数

std::vector<std::shared_ptr<FlightPlan>> allFlightPlans_neighbours(std::vector<std::shared_ptr<Flight>> neighbours, std::string to, std::vector<std::string>> airports, std::vector<std::shared_ptr<Flight>> flights, , std::vector<std::string> visited_airports);

它检查每个邻居并调用原始函数（这些函数是相互递归的）以获得路由。然后，它将这条路由附加到在其余邻居上调用该函数的结果中。

原始函数还有一个 add_each 函数，该函数将表示起始机场 (from) 的 from 字符串、表示目的地机场 (to) 的 to 字符串和路线作为参数。它为路线中的每个飞行计划添加一个航班，以确保生成的所有路线都是完整的。

我想知道是否有一种更简单的方法来编写函数allFlightPlans，可能是一种使用不同参数和/或不同算法方法的方法？看来我的方法比它应该的要复杂。

标签： c++stringoopvectorgraph