php - 寻路算法找到从一个地方到另一个地方的路线

Question

我有 2 个表 schedules 和 places。

我的日程表如下

- Id
- From Place Id
- To Place Id
- Departure Time
- Arrival Time

我的places 表如下

- Id
- Name

例如:当用户搜索从 place_id 5 到 place_id 1 的路线时，系统应该返回一个包含时间表数组的路线数组。例如，该时间表可能如下所示

[
    {
         from_place_id: 5,
         to_place_id: 3,
         ...
    },
    {
         from_place_id: 3,
         to_place_id: 8,
         ...
    },
    {
         from_place_id: 8,
         to_place_id: 1,
         ...
    },
]

我知道有很多算法，比如广度优先搜索、深度优先搜索等。我从来没有用 Laravel eloquent 做过。请给我一些关于实现结果的提示。有许多网站介绍了可用的不同算法，但没有一个对其进行解释。

Answer 1

要找到路径，您必须根据您的时间表构建图形数据结构。您可以从时间表中获取所有记录并从中构建图表。

对于这种情况，您可以使用 bfs 或 dfs。但是 IMO，最好使用 bfs，因为 dfs 不适用于在基于距离的图中查找最短路径。以防将来您会在日程安排表中应用距离。

您还必须考虑您的日程安排数据中的出发和到达时间。这意味着在你的 bfs 实现中，当前地点的下一条路线的出发时间不能小于当前节点的到达时间。