Dijkstra算法是一种用于解决最短路径问题的贪心算法,它的基本思想是:维护从源节点到各个节点的最短距离,并依次将距离最短的节点加入到已经求得最短路径的节点集中。这里我们给出Dijkstra算法的正确性证明。
假设有一张具有 $n$ 个节点和 $m$ 条边的加权无向图 $G=(V,E)$,其中 $V$ 表示节点集合,$E$ 表示边的集合。另外,设 $d_i$ 表示从源节点 $s$ 到节点 $i$ 的最短路径长度,$S$ 表示已经求得最短路径的节点集合,$U=V-S$ 表示未确定最短路的节点集合。
我们需要证明的是,Dijkstra算法可以正确求得从 $s$ 到任意节点的最短路径。
首先,根据算法的基本思想,我们可以将未确定最短路径的节点按照 $d_i$ 从小到大的顺序加入到 $S$ 集合中,然后依次更新其它节点的最短路径长度。具体来说,Dijkstra算法执行过程中,对于每个未确定最短路径的节点 $v\in U$,有以下两个操作:
1.对于 $v$ 的每个邻居节点 $u$,更新 $s$ 到 $u$ 的最短路径长度 $d_u$,使 $d_u=min{d_u,d_v+w(u,v)}$,其中 $w(u,v)$ 表示边 $(u,v)$ 的权值。
2.寻找距离最短的节点 $x$,使 $x\in U$ 且 $d_x$ 最小,将 $x$ 加入到 $S$ 集合中。
在算法执行的过程中,我们可以维护一个数组 $d$,表示当前得知的从 $s$ 到各个节点的最短路径长度。
下面我们来证明 Dijkstra 算法的正确性。我们可以用反证法来证明。
假设 Dijkstra 算法无法找到最短路径
设 $v$ 是加权无向图 $G$ 的一个节点,且 $d_v$ 是从 $s$ 到 $v$ 的最短路径长度。当我们的算法运行时,我们将按照距离 $s$ 的距离从小到大的顺序考虑所有的节点。设 $u$ 表示在我们算法的执行过程中被加入 $S$ 集合的最后一个节点。
根据上述算法的第二个操作,即每次将离 $s$ 最近的未定点加入到 $S$ 集合中,我们可以得出:
$d_u\leq d_v$
若 $d_u> d_v$,则必表明在 $d_v$ 被加入到 $S$ 集合之前,$d_u$ 已经被加入到 $S$ 集合中,这样就与算法中对未确定最短路的节点依次求取距离最小的节点的操作相矛盾了。
在节点 $u$ 加入 $S$ 后,从 $s$ 到 $v$ 的最短路径长度不会再发生变化
我们通过交叉考虑两个点 $u$ 和 $v$ 来证明这个结论:
如果从 $s$ 到 $u$ 的最短路径已经确定,那么对于 $u$ 的所有出边 $(u,x)$ 来说,它们的终点 $x$ 相对于 $s$ 的最短路径长度$d_x$ 就已经确定了。因为除了最短路径长度之外,两个顶点之间没有其他度量,所以如果 $u$ 成为 $S$ 中的节点,并且 $v$ 还没有,则 $d_v$ 长度一定等于 $s$ 到 $v$ 的最短路径的长度,此时具有如下的式子:
$d_u+\omega (u,v)\leq d_v$
因此,对于 $v\in V\backslash S$,我们都有:
$d_u+\omega (u,v)\leq d_v$
如果路径 $\pi$ 是从 $s$ 到 $v$ 的一条最短路径,且 $\pi$ 经过了 $u$,那么必定有:
$d_u+\omega (u,v)=d_v$
否则,如果 $d_u+\omega(u,v) < d_v$,那么我们可以通过 $\pi$ 和 $(u,v)$ 组成的新路径将$d_v$ 更改为$d_u+\omega(u,v)$,这就与原假设存在最短路径 $\pi$ 矛盾了。 如果 $d_u+\omega(u,v)>d_v$,那么它与$d_u+\omega(u,v)\leq d_v$ 矛盾。
因此,可以看出从 $s$ 到 $v$ 的最短路径长度 $d_v$ 不会再发生变化,所以Dijkstra算法可以正确找到最短路径。
因此,综上所述,Dijkstra算法是正确的。