《算法导论》-- 单源最短路径+PHP实现

1.几个定义

1.1 最短路径

定义从节点u到节点v的最短路径权重δ(u, v)如下：

image.png

从节点u到节点v的最短路径则定义为任何一条权重为w(p) = δ(u, v)的从u到v的路径p。

1.2 负权重的边

某些单源最短路径问题可能包括权重为负值的边。但如果图G(V,E)不包含从源结点s可以到达的权重为负值的环路，则对于所有的结点v∈V，最短路径权重δ(u, v)都有精确定义，即使其取值为负数，如果G包含从s可到达的权重为负值的环路，则最短路径权重无定义。从s到该环路的任一结点的路径都不可能是最短路径，因为我们只要不沿着任何“最短”路径再遍历一次权重为负值的环路，则总是可以找到一条权重更小的路径。

1.3 环路

一条最短路径不能包含权重为负值的环路，也不能包含权重为正值的环路，因为只要将环路从路径上删除就可以得到一条源结点和终结点与原来路径相同的一条权重更小的路径。

1.4 松弛操作

对于每个结点v来说，我们维持一个属性v.d，用来记录源结点s到节点v的最短路径权重的上界。我们称v.d为s到v的最短路径估计。我们使用下面运行时间为Θ(V)的算法来对最短路径估计和前驱结点进行初始化：

INIT(G, s)
for each vertex v ∈ G.V
    v.d = ∞
    v.π = NIL
s.d = 0

对一条边（u, v）的松弛过程为：首先测试一下是否可以对从s到v的最短路径进行改善。测试的方法是：将当下s到u的最短路径距离加上u到v之间的边权重，并与当前的s到v的最短路径估计进行比较，如果前者更小，则对v.d和v.π进行更新。

RELEX(u, v,  w)
if v.d > u.d + w(u, v)
    v.d = u.d + w(u, v)
    v.π = u

2. Bellman-Ford算法（贝尔曼-福特算法）

Bellman-ford算法解决的是一般情况下的单源最短路径问题，在这里，边的权重可以为负值，但不能包含负环路，如果存在负环路则返回false。效率较低，为O(VE)。

注：为什么要进行V-1次循环对边松弛，这是因为V个顶点的话，最长路径可能是包含V-1条边（非环路），这意味在这种情况下，最多要进行V-1次松弛。

2.1 伪代码实现

BELLMAN-FORD(G, w ,s)
INIT(G, s)
for i = 1 to |G.V| - 1
    for each edge(u, v) ∈ G.E
        RELAX(u, v, w)
for each edge(u, v) ∈ G.E
    if v.d > u.d + w(u, v)
          return FALSE
return TRUE

2.2 伪代码执行过程

书中给出的流程是这样的：

image.png
这让我非常困惑，困扰了我很久，经过查证，看看这个神奇的网站visualgo, 代码真正的执行流程。
image.png
其实书中给出的不是伪代码的执行流程，这应该是用队列优化后的执行流程，即类似广度优先地对边进行松弛。网上很多人贴上伪代码，就画个优化后的执行流程图，其实是对不上的，一点都不严谨。

2.3 PHP 实现（队列优化版本——SPFA算法）

原版本的算法效率比较低，就不写了，写一个队列优化版本的，被称为SPFA算法。
首先随手画了个有向图，渣渣水平将就，怕画简单了又说明不了问题，索性画一个复杂一点的：

image.png

接下来是写程序：

<?php
class Node {
    public $val; //值
    public $d; //距离
    public $p; //父节点
    public $linkedNodes = [];//连接的顶点
    public function __construct($val)
    {
        $this->val = $val;
    }
}


/**
* SPFA
**/
class Bellman
{
    /**
     * 生成图
     * @param array $vertex
     * @return array
     */
    public function buildGraph($vertex)
    {
        $graph = [];
        $nodes = array_keys($vertex);
        foreach ($nodes as $node) {
            $graph[$node] = new Node($node);
        }
        foreach ($vertex as $key => $item) {
            foreach ($item as $value) {
                if (isset($graph[$value])) {
                    $graph[$key]->linkedNodes[] = $graph[$value];
                }
            }
        }
        return $graph;
    }

    /**
     * 初始化操作
     * @param array $graphNodes
     * @param Node $s
     */
    public function init(&$graphNodes, &$s)
    {
        foreach ($graphNodes as $graphNode) {
            $graphNode->d = 9999999;
        }
        $s->d = 0;
    }

    /**
     * 松弛操作
     * @param Node $u
     * @param Node $v
     * @param Array $w
     * @return bool
     */
    public function relax(&$u, &$v, $w)
    {
        $d = $u->d + $w[$u->val . '_' . $v->val];
        if($v->d > $d) {
            $v->d = $d;
            $v->p = $u;
            return true;
        }
        return false;
    }

    /**
     * Bellman-Ford 算法 [队列优化后的，非原始算法]
     * 问题1：没考虑到负环路
     * @param $graphNodes
     * @param $s
     */
    public function bellManFord(&$graphNodes, $s, $w)
    {
        $num = count($graphNodes) - 1;//最大松弛次数
        $this->init($graphNodes, $s);
        $queue = [];
        $relaxNum = []; //边的松弛次数
        array_push($queue, $s);
        while (!empty($queue)) {
            $node = array_shift($queue);
            foreach ($node->linkedNodes as $linkedNode) {
                if($this->relax($node, $linkedNode, $w)) {
                    $edge = $node->val . '_' . $linkedNode->val;
                    $relaxNum[$edge] = isset($relaxNum[$edge]) ? $relaxNum[$edge] + 1 : 1; //松弛次数+1
                    if($relaxNum[$edge] > $num) {
                        throw new Exception('存在负环！');
                    }
                    if(!in_array($linkedNode, $queue)) {
                        array_push($queue, $linkedNode);
                    }
                }
            }
        }
    }
}


//顶点
$vertex = [
    'a' => ['b', 'd'],
    'b' => ['c'],
    'd' => ['e'],
    'c' => ['f', 'b', 'e'],
    'e' => [],
    'f' => ['c']
];
//边的权重
$w = [
    'a_b' => 2,
    'a_d' => 1,
    'b_c' => 1,
    'd_e' => 3,
    'c_b' => -1,
    'c_f' => 1,
    'c_e' => 2,
    'f_c' => -3
];

$g = new Bellman();
$graphNodes = $g->buildGraph($vertex);
$g->bellManFord($graphNodes, $graphNodes['a'], $w);

好，运行一下代码，嚓！！！

image.png

MMP，我画图画的那么辛苦，居然画了个有负环的，还傻乎乎的画了路径，将错就错也懒的改了。
负环在这里：

image.png

改下数据，把 'f_c' => -3改成-1，运行一下：

image.png

3. Dijkstra算法（迪杰斯特拉算法）

Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有的边的权重都为非负值。

3.1 伪代码实现

DIJKSTARA(G, w, s)
INIT(G, s)
S = ∅
Q =G.V
while Q ≠ ∅
    u = EXTRACT-MIN(Q) //最小优先队列Q,排序关键字为顶点的d值
    S = S U {u}
    for each vertex v ∈ G.Adj[u]
        RELAX(u, v, w)

3.2 伪代码执行过程

image.png

3.3 PHP 实现

图：

image.png

a是起点，最短距离:

image.png

<?php
class Node {
    public $val; //值
    public $d; //距离
    public $p; //父节点
    public $linkedNodes = [];//连接的顶点
    public function __construct($val)
    {
        $this->val = $val;
    }
}


/**
 * Dijkstra
 **/
class DijkstraAlgorithm
{
    /**
     * 生成图
     * @param array $vertex
     * @return array
     */
    public function buildGraph($vertex)
    {
        $graph = [];
        $nodes = array_keys($vertex);
        foreach ($nodes as $node) {
            $graph[$node] = new Node($node);
        }
        foreach ($vertex as $key => $item) {
            foreach ($item as $value) {
                if (isset($graph[$value])) {
                    $graph[$key]->linkedNodes[] = $graph[$value];
                }
            }
        }
        return $graph;
    }

    /**
     * 初始化操作
     * @param array $graphNodes
     * @param Node $s
     */
    public function init(&$graphNodes, &$s)
    {
        foreach ($graphNodes as $graphNode) {
            $graphNode->d = 9999999;
        }
        $s->d = 0;
    }

    /**
     * 松弛操作
     * @param Node $u
     * @param Node $v
     * @param Array $w
     * @return bool
     */
    public function relax(&$u, &$v, $w)
    {
        $d = $u->d + $w[$u->val . '_' . $v->val];
        if($v->d > $d) {
            $v->d = $d;
            $v->p = $u;
            return true;
        }
        return false;
    }

    /**
     * 从队列取出最小距离的顶点
     * @param array $queue
     */
    public function extractMin(&$queue)
    {
        $result = [];
        foreach ($queue as $item) {
            $result[$item->d] = $item;
        }
        ksort($result);
        $queue = array_values($result);
        return array_shift($queue);
    }

    /**
     * Dijkstra 算法
     * 问题1：没考虑到负环路
     * @param $graphNodes
     * @param $s
     */
    public function dijkstra(&$graphNodes, $s, $w)
    {
        $this->init($graphNodes, $s);
        $gather = [];
        $queue = $graphNodes;
        while (!empty($queue)) {
            $node = $this->extractMin($queue);
            $gather[] = $node;
            foreach ($node->linkedNodes as $linkedNode) {
                if($this->relax($node, $linkedNode, $w)) {
                    if(!in_array($linkedNode, $queue)) {
                        array_push($queue, $linkedNode);
                    }
                }
            }
        }
    }
}


//顶点
$vertex = [
    'a' => ['b', 'c'],
    'b' => ['d'],
    'd' => ['e'],
    'c' => ['e'],
    'e' => [],
];
//边的权重
$w = [
    'a_b' => 1,
    'a_c' => 3,
    'b_d' => 2,
    'd_e' => 2,
    'c_e' => 4,
];

$g = new DijkstraAlgorithm();
$graphNodes = $g->buildGraph($vertex);
$g->dijkstra($graphNodes, $graphNodes['a'], $w);

执行结果：

image.png