Dijkstra算法浅理解

22.11.10更新：之前大一初学时尝试“严谨”证明，但现在来看只是感性陈述了一番。上个星期，在算法课上学习了算法导论上从路径松弛性质出发的证明，回顾一下自己之前的思路，同时完善之前的公式表达。

---

数学建模书中的算法描述：

设所考虑的图为$N=N(V,A,W)$，其中$V=v_1,v_2,\dots ，v_n$，即顶点个数$|V|=n$，$E$为弧边的集合，其弧边的条数为$|E|=m$；$W=(w_{ij}{)}_{n\ast n}$为权值邻接矩阵，$wij$为边$(v_i,v_j)$的权值，满足$w_{ij}\ge 0$，如果$(v_i,v_j)\notin E$，则$w_{ij}=\infty$.
设$v_1$为起点（源点），记$d(v_j)$表示从源点$v_1$到$v_j$的只允许经过已选出的顶点的最短路的权值（路长），即最短路上的点均属于已选出的顶点集合。

算法步骤：

1、输入权值邻接矩阵$W$，令$d(v_1)=0,d(v_j)=w_{1j},j\in [2,n],S=v_1,R=V/S_1=v_2,\dots ,v_n$($S$中的点给永久记号，$R$中的点給临时记号）;

（标记这一步将点分成了两个集合，$S$集合给永久记号意味着对应点$v_k$对应的$d(v_k)$不会再改变）
2、在$R$中取一点$v_k$,使得 d ( v k ) = m i n { d ( v j ) , v j ∈ R } d(v_k) = min\{d(v_j),v_j∈R\} d(vk​)=min{d(vj​),vj​∈R}，如果$d(v_k)=+\infty$，停止向下搜索，即从$v_1$到$R$中的点没有路，否则转第三步;
3、令$S=S\cup v_k,R=R/v_k$,（$k$改为永久记号）。如果$R=\varnothing$，结束，所有各点的最短路都已经求得；否则转第四步；
4、对于每一个$v_j\in R$，修正 d ( v j ) = m i n { d ( v j ) , d ( v k ) + w k j } d(v_j)=min\{d(v_j),d(v_k)+w_{kj}\} d(vj​)=min{d(vj​),d(vk​)+wkj​}，返回第二步。

---

理解1：为什么可以求得最短路?

算法实际上运用了动态规划的思想，每次我从$R$集合中选取一个离$v_1$的最近点$v_k$，用它去修正$d()$这个以已选取点（就是$S$集合中的点）作为内点的最短路数组，每次这个内点集合都会增加一个点，最后所有的点（不可到达点除外）都会被选进这个内点集合，我们所得到的$d()$就是以图上所有点为内点的和$v_1$之间最短路数组，而这也就是$v_1$的所有单源最短路数组，是$v_1$和所有其他点的最短路数组。

理解2：为什么每次选进S集合的点，都能保证已经求得$v_1$和它的最短路？

首先我们要清楚一个事实，即每次选进$S$集合的点$v_k$，它所对应的$d(v_k)$大于任意已经选进$S$集合的点的$d$，换一种说法，用$v_k$修正后$d$不小于$d(v_k)$，因为修正的时候 d ( v j ) = m i n { d ( v j ) , d ( v k ) + w k j } , d ( v j ) ≥ d ( v k ) d(v_j) = min\{d(v_j),d(v_k)+w_{kj}\},d(v_j)\geq d(v_k) d(vj​)=min{d(vj​),d(vk​)+wkj​},d(vj​)≥d(vk​)；
若我们选进$S$集合的点，并未求得$v_1$到它的最短路（反证法），则说明到该点的最短路内点不只有之前已选进$S$集合的点。设最短路还包括内点$a,a\in R$，这样的话，在之后的步骤中，我们会以$d(a)$修正$d(v_k),v_k\in S$，而根据之前我们的结论$d(v_k)\le d(a)$，$d(v_k)$并不会被修改。所以每次选进$S$集合的点，我们都能保证已经求得$v_1$和它的最短路。

---

理解1中提及dp，实质上松弛操作就是一步递推，用公式表达就是递推公式。理解2说明了点$v$选进集合$S$之后，$d(v)$不再变化，有点算导中证循环不变式的意味，但是无法保证$d(v)$就是最短路，没有阐述为何收敛，这是否可以通过前面dp公式补充？dp公式的正确性最终应通过收敛性保证吧。