dijkstra算法 PHP实现
Dijkstra算法PHP实现
Dijkstra算法用于在加权图中找到单源最短路径。以下是PHP实现的关键步骤和代码示例：
初始化数据结构
需要准备三个数组：$dist存储节点到起点的最短距离，$visited标记节点是否已处理，$graph表示图的邻接矩阵。
$graph = [
'A' => ['B' => 6, 'D' => 1],
'B' => ['A' => 6, 'D' => 2, 'E' => 2],
'D' => ['A' => 1, 'B' => 2, 'E' => 1],
'E' => ['B' => 2, 'D' => 1]
];核心算法实现
使用优先队列（或遍历查找）每次选择当前距离起点最近的未处理节点。
function dijkstra($graph, $start) {
$dist = [];
$visited = [];
$queue = new SplPriorityQueue();
foreach ($graph as $vertex => $adj) {
$dist[$vertex] = INF;
$visited[$vertex] = false;
}
$dist[$start] = 0;
$queue->insert($start, 0);
while (!$queue->isEmpty()) {
$u = $queue->extract();
$visited[$u] = true;
foreach ($graph[$u] as $v => $weight) {
if (!$visited[$v] && $dist[$v] > $dist[$u] + $weight) {
$dist[$v] = $dist[$u] + $weight;
$queue->insert($v, -$dist[$v]); // 使用负数模拟最小堆
}
}
}
return $dist;
}结果输出
调用函数并打印最短路径结果：
$startNode = 'A';
$shortestPaths = dijkstra($graph, $startNode);
foreach ($shortestPaths as $node => $distance) {
echo "Shortest distance from $startNode to $node is $distance\n";
}复杂度分析
时间复杂度为O(V^2)（使用数组）或O(E + V log V)（使用优先队列），其中V是顶点数，E是边数。空间复杂度为O(V)。
注意事项
- 确保图为非负权图
- 未连接的节点距离保持INF
- 实际应用时可能需要添加路径回溯功能
