php - 起点和终点列表的基本非加权寻路

Question

我正在制作一个旅游项目，但我遇到了一个问题。我创建了一个数据库：

ID  Source   Destination

1     C1         C2
2     C3         c4
3     C3         C5
4     C4         C6
5     C8         C9
6     C2         C3

当我从 C1->C6 进行游览时，它应该遵循路径 c1->c2->c3->c4->c6。但是当通过查询检索时，我在到达 c3 时遇到了冲突：还有另一个 C3->c5。

我该如何克服这个问题？

首先，我通过签入 mysql 将 c1 作为源，从该目的地获取目的地作为源检查相关目的地

Answer 1

尝试：

CREATE TABLE test (
  ID INTEGER NOT NULL,
  SOURCE CHAR(2) NOT NULL,
  DESTINATION CHAR(2) NOT NULL
);

INSERT INTO test VALUES (1, 'C1', 'C2');
INSERT INTO test VALUES (2, 'C3', 'C4');
INSERT INTO test VALUES (3, 'C3', 'C5');
INSERT INTO test VALUES (4, 'C4', 'C6');
INSERT INTO test VALUES (5, 'C8', 'C9');
INSERT INTO test VALUES (6, 'C2', 'C3');

然后：

SELECT
  CONCAT_WS(
    '->',
    A.SOURCE,
    A.DESTINATION,
    B.DESTINATION,
    C.DESTINATION,
    D.DESTINATION
  )
FROM test A
LEFT JOIN test B ON B.SOURCE = A.DESTINATION
LEFT JOIN test C ON C.SOURCE = B.DESTINATION
LEFT JOIN test D ON D.SOURCE = C.DESTINATION
WHERE
  A.SOURCE = 'C1'
  AND 'C6' IN (A.DESTINATION, B.DESTINATION, C.DESTINATION, D.DESTINATION);

这使：

C1->C2->C3->C4->C6

请记住，此示例仅给出最大深度为 4 的路径，但您可以轻松扩展它。此外，您将获得所有可能的路径（如果有多个）。所以你需要决定你选择哪一个。

Answer 2

1）您可以通过将数据存储到树中来解决，并使用算法到达目的地：

2）使用数组和递归的简单解决方案：

这里复杂的部分只是带来“提到的源和目标所需的数据”，即离开 c8->c9

我havnt工作做带来foll数据。但是，你可以继续： $destination['c1'] = 'c2'; $目的地['c3'][] = 'c4'; $destination['c4'] = 'c6'; $destination['c2'] = 'c3';

$route = array();
$int = 0;

function route_to($route,$source_statn, $dest_statn) {
    global $int, $destination,$path;

    if ($source_statn != '' && $dest_statn != '') {
        if ($destination[$source_statn] == $dest_statn) {
            $route[++$int] = "$source_statn -> {$destination[$source_statn]}";

            $path = $route;
            return $path;
        } else {
            if (is_array($destination[$source_statn])) {
                foreach ($destination[$source_statn] as $each) {
                    $route[++$int] = "$source_statn -> $each";
                    route_to($route,$each, $dest_statn);
                }
            } else {
                if($destination[$source_statn] != ''){
                    $route[++$int] = "$source_statn -> {$destination[$source_statn]}";
                }
                route_to($route,$destination[$source_statn], $dest_statn);
            }
        }
    }
}

route_to($route,'c1','c6');

echo '<pre>path';
print_r($path);
echo '</pre>';

---------o/p------------

Array
(
    [1] => c1 -> c2
    [2] => c2 -> c3
    [3] => c3 -> c4
    [4] => c4 -> c6
)