PHP 解决最短路径问题

在二维地图上寻找从A点到B点的最短路径是一项常见的任务，通常可以使用图算法来解决。常用的算法包括广度优先搜索（BFS）、Dijkstra算法和A*算法。

使用广度优先搜索（BFS）算法寻找最短路径

广度优先搜索是一种简单而有效的算法，对于在无权图（即每条边的权重相同）中寻找最短路径非常适用。以下是在PHP中实现BFS算法的示例：

<?php
class Point {
    public $x;
    public $y;

    public function __construct($x, $y) {
        $this->x = $x;
        $this->y = $y;
    }

    public function __toString() {
        return "($this->x, $this->y)";
    }
}

function bfs($map, $start, $end) {
    $rows = count($map);
    $cols = count($map[0]);
    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // 右, 下, 左, 上
    $queue = new SplQueue();
    $queue->enqueue([$start, [$start]]); // 队列中存储当前点和路径
    $visited = [];

    while (!$queue->isEmpty()) {
        list($current, $path) = $queue->dequeue();
        $x = $current->x;
        $y = $current->y;

        if ($x == $end->x && $y == $end->y) {
            return $path; // 找到路径
        }

        foreach ($directions as $direction) {
            $newX = $x + $direction[0];
            $newY = $y + $direction[1];
            $newPoint = new Point($newX, $newY);

            if ($newX >= 0 && $newX < $rows && $newY >= 0 && $newY < $cols && $map[$newX][$newY] == 0 && !isset($visited["$newX,$newY"])) {
                $queue->enqueue([$newPoint, array_merge($path, [$newPoint])]);
                $visited["$newX,$newY"] = true;
            }
        }
    }
    return null; // 无路径
}

// 示例地图：0表示可以通行，1表示障碍物
$map = [
    [0, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0]
];

$start = new Point(0, 0);
$end = new Point(4, 4);

$path = bfs($map, $start, $end);

if ($path) {
    echo "Path found:\n";
    foreach ($path as $point) {
        echo $point . " ";
		// output: (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4) 
    }
} else {
    echo "No path found.";
}
?>

代码解释：

• Point类：用于表示地图上的点。
• bfs函数：实现广度优先搜索算法，接收地图、起点和终点作为参数，返回从起点到终点的路径。
• directions数组：表示四个可能的移动方向（右、下、左、上）。
• 队列（SplQueue）：用于存储当前点和路径。
• visited数组：用于标记已访问的点，避免重复访问。

运行结果：

如果找到路径，程序将输出从起点到终点的路径。如果没有路径，则输出“无路径”。

总结：

广度优先搜索适用于在无权图中寻找最短路径。如果地图中有不同权重的边或者需要考虑效率，可以考虑使用Dijkstra算法或A*算法。