1. l(u₀)=0,l(v)=∞,∀v∈V,v≠u₀,S={u₀},i=0;
2. ~S=V-S,如果~S=∅,则停止，否则对∀v∈~S，令 l(v)=min(l(v),l(u_i)+w(u_i,v))
3. 求u_i+1,使得l(u_i+1)=min(l(v),∀v∈~S)
4. S=S∐{u_i+1},i=i+1
5. 转到步骤2

这个算法为何正确？

这里是详细的证明。

用PHP实现该算法如下：

function dijksrta($matrix,$from,$to)
{
    $n = count($matrix);

    for($i = 0; $i < $n; $i++)
    {
        if($i != $from)
        {
            $l[$i] = PHP_INT_MAX;
            $v[] = $i;
        }
        else
        {
            $l[$i] = 0;
            $s[] = $i;
        }
    }
    $current = $from;
    while(sizeof($s) < $n)
    {
        $d = -1;
        $nextindex = -1;
        foreach($v as $index => $node)
        {
            $l[$node] = min($l[$node],$l[$current] + $matrix[$current][$node]);
            if($d < 0 || $l[$node] <= $d)
            {
                $d = $l[$node];
                $nextindex = $index;
            }
        }
        if($v[$nextindex] == $to)
        {
            var_dump($l[$to]);
            return;
        }
        $s[] = $v[$nextindex];
        $current = $v[$nextindex];
        unset($v[$nextindex]);
    }
}

用下图中的数据进行测试：

$matrix = array(
                array(0,7,9,PHP_INT_MAX,PHP_INT_MAX,14),
                array(7,0,10,15,PHP_INT_MAX,PHP_INT_MAX),
                array(9,10,0,11,PHP_INT_MAX,2),
                array(PHP_INT_MAX,15,11,0,6,PHP_INT_MAX),
                array(PHP_INT_MAX,PHP_INT_MAX,PHP_INT_MAX,6,0,9),
                array(14,PHP_INT_MAX,2,PHP_INT_MAX,9,0)
            );
$from = 0;
$to = 4;
dijksrta($matrix,$from,$to);

输出：int(20)

更新：

今天再来分析它的原理，可以概括为：

1. 集合A中的某特定点到集合B的最短路径若节点数>=3，则倒数第2个必定属于A。
2. 集合A中某特定点到集合B的最短路径必然也是对应两点间的最短距离。
3. 把两点间最短路径的问题转化为两个集合间最短路径的问题，单纯这样转的话复杂度是i(n-i)的累计，即O(n^3),利用DP将中间的计算结果巧妙的缓存下来，可以转为O(n^2)，缓存方法见篇首。