当前位置：首页 > PHP

dijkstra php实现

2026-02-14 14:35:51PHP

Dijkstra算法PHP实现

Dijkstra算法是一种用于在加权图中查找单源最短路径的经典算法。以下是PHP实现的关键步骤和代码示例：

基础实现思路

创建一个优先队列（最小堆）来存储节点及其当前已知的最短距离。初始化所有节点的距离为无穷大，除了起点设置为0。每次从队列中取出距离最小的节点，更新其邻居节点的距离。

完整代码实现

class Dijkstra {
    public function shortestPath($graph, $start) {
        $distances = [];
        $visited = [];
        $priorityQueue = new SplPriorityQueue();

        foreach ($graph as $vertex => $adj) {
            $distances[$vertex] = INF;
        }
        $distances[$start] = 0;

        $priorityQueue->insert($start, 0);

        while (!$priorityQueue->isEmpty()) {
            $currentVertex = $priorityQueue->extract();

            if (isset($visited[$currentVertex])) {
                continue;
            }
            $visited[$currentVertex] = true;

            foreach ($graph[$currentVertex] as $neighbor => $weight) {
                $alt = $distances[$currentVertex] + $weight;
                if ($alt < $distances[$neighbor]) {
                    $distances[$neighbor] = $alt;
                    $priorityQueue->insert($neighbor, -$alt);
                }
            }
        }

        return $distances;
    }
}

// 示例图结构（邻接表表示）
$graph = [
    'A' => ['B' => 3, 'C' => 5],
    'B' => ['A' => 3, 'C' => 1, 'D' => 2],
    'C' => ['A' => 5, 'B' => 1, 'D' => 3],
    'D' => ['B' => 2, 'C' => 3]
];

$dijkstra = new Dijkstra();
$result = $dijkstra->shortestPath($graph, 'A');
print_r($result);

关键注意事项

PHP的SplPriorityQueue默认是最大堆，因此插入时使用负值来模拟最小堆行为。确保图的表示采用邻接表形式，其中每个节点包含其邻居及对应边的权重。

对于大型图，考虑使用更高效的优先队列实现或优化存储结构。算法时间复杂度为O((V+E)logV)，其中V是顶点数，E是边数。

路径追踪扩展

若要记录完整路径而不仅是距离，可添加前驱节点记录：

$previous = [];
// 在更新距离时添加
if ($alt < $distances[$neighbor]) {
    $distances[$neighbor] = $alt;
    $previous[$neighbor] = $currentVertex;
    $priorityQueue->insert($neighbor, -$alt);
}

路径重建函数可通过回溯前驱节点数组生成从起点到任意节点的具体路径。

dijkstra php实现