清溪算法 2020-01-17
作为求解最短路问题的算法中最稳健的算法,Dijkstra以其惊奇的操作和独特的魅力,吸引了无数OIer学习、钻研。身为一名蒟蒻,本人以有限的能力付诸仔细的思考,对于Dijkstra算法中贪心思想的正确性有了新的认识。
咳咳,相信我,这是一篇很正常的博客,本人也是一名很正常的博主。
大多数OIer在初学Dijkstra算法时都不求甚解,单纯的把板子背下来就算了,而对于其中的贪心思想的内涵并没有做过深入挖掘。对于其贪心算法的正确性,我以我个人的理解,进行非严格的证明,希望有助于大家理解Dijkstra算法。
回顾Dijkstra算法的流程:
1. 初始化dis[1]=0,其余节点的dis值置为正无穷。
2. 找出一个未被标记的、dis[k]最小的节点k,标记。
3. 遍历节点k的所有出边,进行松弛操作。
4. 重复步骤2~3,直到所有节点均被标记。
不难发现,该算法正确的关键,就在于每次找出的节点k必然已是起点到k的最短路径。基于此,当所有节点都被标记时,就相当于所有节点的最短路均已被求解,算法结束。
故而,要证明该算法的正确性,实际上只需证明每次找出的节点必然已经是起点到k的最短路径即可。
由于每次都会标记一个点,故等到所有点全部标记,循环的重复次数即为节点数n。
下面考虑证明。
证明:
对于起点,dis[1]=0,显然正确。
考虑第一次循环。
由于只有dis[1]有值,其余均为正无穷,故第一次找到的节点必然为起点。
接下来的操作是遍历该点的出边。
假设由起点出发的边指向的点为v1、v2、……、vs。
只需证明松弛以上各点后,各点中的dis值最小者其dis值必然已是最短路即可。
反证法:
设v1、v2、……、vs中dis值最小者为vm。
假设该点此时的dis值不是起点到m的最短路径。
则必然可以找到一条路径:起点 → vx →……→vm,使该路径的长度小于此时的dis[m]。
其中vx是v1、v2、……、vs中的某点。
根据假设,由于m点是从起点出发经过一条边直接达到的所有点中长度最小的,因而该路径中起点 → vx这一步的长度必然大于等于起点 → vm的长度,由于边权均非负,因而该路径的总长度必然不可能小于此时的dis[m]。
矛盾!
故这一步找到的m点必然已经找到了最短路。
而下一步也必然会拿m点进行松驰。循环重复,直至所有点都被找到最短路。
故该算法正确性成立。
证毕!
其实上述证明过程实际也解释了为何Dijkstra算法只适用于边权非负的情况。如果边权不满足均非负,则正确性无法得到证明。