时间戳

首页 > 解决方案 > 路径查找算法来查找从一个地方到另一个地方的路线

php - 路径查找算法来查找从一个地方到另一个地方的路线

问题描述

我有 2 张桌子schedules和places.

我的schedules表如下

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

我的places表如下

- Id
- Name

例如：当用户搜索从place_id5 到place_id1 的路线时，系统应该返回一个包含日程数组的路线数组。例如，该时间表可能如下所示

[
    {
         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 做过这些算法。请给我一些关于实现结果的提示。有许多网站介绍了可用的不同算法，但没有一个网站对此进行了解释。

标签： phpmysqllaravelalgorithmpath-finding

解决方案

根据我从您的问题中了解到的情况，请尝试以下代码：

$schedules = Schedule::where('from_place_id', '!=', $from_place_id)->where('to_place_id', '!=', $to_place_id)->get();

$roots = Schedule::where('from_place_id', $from_place_id)->get();
$goals = Schedule::where('to_place_id', $to_place_id)->get();

$stack = ['schedules' => []];

foreach ($roots as $root) {
    $travelTime = date('H:i:s', $this->timeDiff($root->departure_time, $root->arrival_time));
    $root['travel_time'] = $travelTime;
    $child = [$root];

    $requiredTime = $this->timeDiff($departure_time, $root->departure_time);

    if ($requiredTime >= 0) {
        foreach ($schedules as $schedule) {
            $previous = $child[count($child) - 1];

            $timeDiff = $this->timeDiff($previous->arrival_time, $schedule->departure_time);

            if ($schedule->from_place_id == $previous->to_place_id &&
        $timeDiff >= 0 && $timeDiff <= 3600) {
                $travelTime = date('H:i:s', $this->timeDiff($schedule->departure_time, $schedule->arrival_time));
                $schedule['travel_time'] = $travelTime;
                array_push($child, $schedule);

                foreach ($goals as $goal) {
                    $goalTimeDiff = $this->timeDiff($schedule->arrival_time, $goal->departure_time);

                    if ($goal->from_place_id == $schedule->to_place_id &&
                    $goalTimeDiff >= 0 && $goalTimeDiff <= 3600) {
                        $travelTime = date('H:i:s', $this->timeDiff($goal->departure_time, $goal->arrival_time));
                        $goal['travel_time'] = $travelTime;
                        array_push($child, $goal);
                        array_push($stack['schedules'], $child);
                        break 2;
                    }
                }
            }
        }
    }
}

return $stack;

此外，您需要创建一个新的受保护函数，timeDiff如下所示

protected function timeDiff($first, $second)
{
    return Carbon::parse($first)->diffInSeconds(Carbon::parse($second), false);
}

不要忘记在顶部导入Carbon和。Schedule

推荐阅读