当前位置：首页 > PHP

dijkstra php实现

2026-01-29 16:35:06PHP

Dijkstra算法的PHP实现

Dijkstra算法是一种用于在加权图中查找单源最短路径的经典算法。以下是一个完整的PHP实现示例，包含图的表示和算法执行过程。

图的表示

使用邻接数组来表示图结构，每个节点包含其邻居及对应的边权重：

$graph = [
    'A' => ['B' => 6, 'D' => 1],
    'B' => ['A' => 6, 'D' => 2, 'E' => 2],
    'C' => ['B' => 5, 'E' => 5],
    'D' => ['A' => 1, 'B' => 2, 'E' => 1],
    'E' => ['B' => 2, 'D' => 1, 'C' => 5]
];

算法实现

function dijkstra($graph, $start) {
    // 初始化距离数组
    $distances = [];
    foreach (array_keys($graph) as $node) {
        $distances[$node] = INF;
    }
    $distances[$start] = 0;

    // 初始化优先队列
    $queue = new SplPriorityQueue();
    $queue->insert($start, 0);

    // 记录已访问节点
    $visited = [];

    while (!$queue->isEmpty()) {
        $current = $queue->extract();

        if (isset($visited[$current])) continue;
        $visited[$current] = true;

        foreach ($graph[$current] as $neighbor => $weight) {
            $alt = $distances[$current] + $weight;
            if ($alt < $distances[$neighbor]) {
                $distances[$neighbor] = $alt;
                $queue->insert($neighbor, -$alt); // 使用负数实现最小堆
            }
        }
    }

    return $distances;
}

使用示例

$graph = [
    'A' => ['B' => 6, 'D' => 1],
    'B' => ['A' => 6, 'D' => 2, 'E' => 2],
    'C' => ['B' => 5, 'E' => 5],
    'D' => ['A' => 1, 'B' => 2, 'E' => 1],
    'E' => ['B' => 2, 'D' => 1, 'C' => 5]
];

$startNode = 'A';
$result = dijkstra($graph, $startNode);

print_r($result);

输出解释

运行上述代码将输出从节点A到所有其他节点的最短距离：

Array
(
    [A] => 0
    [B] => 3
    [C] => 7
    [D] => 1
    [E] => 2
)

路径追踪改进版

如果需要记录完整路径而不仅仅是距离，可以修改算法如下：

function dijkstraWithPath($graph, $start) {
    $distances = [];
    $previous = [];
    $queue = new SplPriorityQueue();

    foreach (array_keys($graph) as $node) {
        $distances[$node] = INF;
        $previous[$node] = null;
    }
    $distances[$start] = 0;

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

    while (!$queue->isEmpty()) {
        $current = $queue->extract();

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

    return ['distances' => $distances, 'previous' => $previous];
}

function getPath($previous, $target) {
    $path = [];
    $current = $target;

    while ($current !== null) {
        array_unshift($path, $current);
        $current = $previous[$current];
    }

    return $path;
}

$result = dijkstraWithPath($graph, 'A');
$pathToC = getPath($result['previous'], 'C');

print_r($pathToC); // 输出: Array ( [0] => A [1] => D [2] => E [3] => C )