PHP算法设计技巧：如何使用Bellman-Ford算法解决单源最短路径问题？

<?php

class Graph {
    private $vertices;
    private $edges;

    public function __construct($vertices) {
        $this->vertices = $vertices;
        $this->edges = [];
    }

    public function addEdge($start, $end, $weight) {
        $this->edges[] = [$start, $end, $weight];
    }

    public function bellmanFord($source) {
        $distance = [];
        $predecessor = [];

        // 设置源节点到其他所有节点的初始距离为无穷大
        foreach ($this->vertices as $vertex) {
            $distance[$vertex] = INF;
            $predecessor[$vertex] = null;
        }

        $distance[$source] = 0;

        // 对每个节点进行松弛操作
        for ($i = 0; $i < count($this->vertices) - 1; $i++) {
            foreach ($this->edges as $edge) {
                $u = $edge[0];
                $v = $edge[1];
                $w = $edge[2];

                if ($distance[$u] != INF && $distance[$u] + $w < $distance[$v]) {
                    $distance[$v] = $distance[$u] + $w;
                    $predecessor[$v] = $u;
                }
            }
        }

        // 检测负权环
        foreach ($this->edges as $edge) {
            $u = $edge[0];
            $v = $edge[1];
            $w = $edge[2];

            if ($distance[$u] != INF && $distance[$u] + $w < $distance[$v]) {
                echo "图中存在负权环";
                return;
            }
        }

        // 输出最短路径结果
        foreach ($this->vertices as $vertex) {
            echo "节点" . $vertex . "的最短路径长度为： " . $distance[$vertex] . "，路径为： ";
            $path = [];
            $current = $vertex;

            while ($current != $source) {
                array_unshift($path, $current);
                $current = $predecessor[$current];
            }

            array_unshift($path, $source);
            echo implode(" -> ", $path) . "
";
        }
    }
}

$graph = new Graph(["A", "B", "C", "D", "E"]);
$graph->addEdge("A", "B", 4);
$graph->addEdge("A", "C", 1);
$graph->addEdge("C", "B", -3);
$graph->addEdge("B", "D", 2);
$graph->addEdge("D", "E", 3);
$graph->addEdge("E", "D", -5);

$graph->bellmanFord("A");