当前位置：首页 > PHP

dijkstra php实现

2026-02-28 13:49:51PHP

Dijkstra 算法的 PHP 实现

Dijkstra 算法用于在加权图中找到从起点到所有其他顶点的最短路径。以下是一个完整的 PHP 实现示例：

class Dijkstra {
    private $graph;
    private $distance;
    private $previous;
    private $unvisited;

    public function __construct($graph) {
        $this->graph = $graph;
    }

    public function shortestPath($start) {
        $this->initialize($start);

        while (!empty($this->unvisited)) {
            $current = $this->getClosestUnvisitedNode();
            foreach ($this->graph[$current] as $neighbor => $cost) {
                if (isset($this->unvisited[$neighbor])) {
                    $newDistance = $this->distance[$current] + $cost;
                    if ($newDistance < $this->distance[$neighbor]) {
                        $this->distance[$neighbor] = $newDistance;
                        $this->previous[$neighbor] = $current;
                    }
                }
            }
            unset($this->unvisited[$current]);
        }

        return $this->formatResults();
    }

    private function initialize($start) {
        $this->distance = [];
        $this->previous = [];
        $this->unvisited = [];

        foreach (array_keys($this->graph) as $vertex) {
            $this->distance[$vertex] = INF;
            $this->previous[$vertex] = null;
            $this->unvisited[$vertex] = true;
        }

        $this->distance[$start] = 0;
    }

    private function getClosestUnvisitedNode() {
        $minDistance = INF;
        $closestNode = null;

        foreach ($this->unvisited as $node => $value) {
            if ($this->distance[$node] < $minDistance) {
                $minDistance = $this->distance[$node];
                $closestNode = $node;
            }
        }

        return $closestNode;
    }

    private function formatResults() {
        return [
            'distance' => $this->distance,
            'previous' => $this->previous
        ];
    }
}

使用示例

// 定义图结构 (邻接表表示)
$graph = [
    'A' => ['B' => 6, 'D' => 1],
    'B' => ['A' => 6, 'D' => 2, 'E' => 2],
    'C' => ['E' => 5],
    'D' => ['A' => 1, 'B' => 2, 'E' => 1],
    'E' => ['B' => 2, 'D' => 1, 'C' => 5]
];

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

print_r($result);

关键点说明

算法实现分为几个主要部分：

初始化所有节点的距离为无穷大(INF)，起点距离为0
维护未访问节点集合
每次迭代选择距离起点最近的未访问节点
更新该节点邻居的距离
从未访问集合中移除已处理节点

复杂度分析

基础实现的时间复杂度为O(V^2)，其中V是顶点数量。使用优先队列可以优化到O(E + V log V)，其中E是边数。

路径重构

要从结果中重构具体路径，可以反向追踪previous数组：

dijkstra php实现

function reconstructPath($previous, $target) {
    $path = [];
    while (isset($previous[$target])) {
        array_unshift($path, $target);
        $target = $previous[$target];
    }
    array_unshift($path, $target);
    return $path;
}