MIT算法导论公开课之第17课 最短路径算法、Dijkstra算法、广度优先搜索

图的路径

给定一个图G=(V,E)且每条边都通过函数w被赋予一个实数的权值。

最短路径问题

找到图中从顶点u到顶点v的最小权值的路径。

最短路径权值问题：

计算图中从顶点u到顶点v的路径的最小权值。
δ(u,v)=min{w(P),P为从顶点u到顶点v的路径}（存在路径）
δ(u,v)=∞（不存在路径）

无最短路径的情况：

1.图中存在权值和为负数的环形路径。

• Ex：
  
  环形路径走的次数越多，顶点u到顶点v的路径权值越小，所以无最小权值路径。
  2.不存在路径将顶点u和v连接起来。

动态规划思路

• 最优子结构：
  最短路径的子路径也是一条最短路径。
  
  • 剪贴法证明：
    
    从u到v的最短路径如图所示，假设其子路径从x到y不是最短路径，那么只需将从x到y的最短路径剪贴入从u到v的路径中，那么即可得到更短的路径，与从u到v的原最短路径相矛盾，所以假设不成立，最短路径的子路径也是一条最短路径得证。
• 重叠子问题：
  求解从u到v的最短路径，可以划分为求路径中顶点之间最短路径子问题。
  这些子问题具有一定的重叠性。
• 综上可知，最短路径问题可以使用动态规划完成。

三角不等式

对任意的顶点u，v，x∈V，δ(u,v)<=δ(u,x)+δ(x,v)。

• Ex：
  
  由反证法可证明其显然成立。

单源最短路径问题

给定一个源点s，计算从源点s到任意顶点的最短路径权值（即δ(s,v)对任意的v∈V）。
事实证明求从A到B的最短路径问题并不会比求单源最短路径问题简单。
此处为简化问题，假设对任意的u,v∈V，有w(u,v)>=0，且图为连通图，存在最短路径。

贪心算法思路

1.维护一个所有已知最短路径的顶点的集合S。
开始时，S中只有一个元素s，从s到s的距离记为0。
2.每次向S中加入一个顶点v，v∈V-S，且v是离S距离最短（贪心思想）的点。

3.更新到刚加入S的顶点v所邻接的点的估算距离。

Dijkstra算法

    算法伪码：
        d[s] ← 0//d[x]表示从源点到x的预估距离，当x∈S时，d[x]=δ(s,x)。
        for each v∈V-{S}
            d[v] ← ∞
        S ← ∅
        Q ← V//Q表示一个优先级队列，键值为d[v]。
        while Q≠∅
            u ← Extract-Min(Q)
            S ← S∪{u}
            for each v∈Adj[u]
                if d[v]>d[u]+w(u,v)//此处的作用是如果违背三角不等式，那么修正它。
                    d[v] ← d[u]+w(u,v)//此时d[u]=δ(s,u)。
其中的if d[v]>d[u]+w(u,v) d[v] ← d[u]+w(u,v)，被称为松弛法（relaxation step）。

注：
Relaxation is making a change that reduces constraints. When the Dijkstra algorithm examines an edge, it removes an edge from the pool, thereby reducing the number of constraints.
One of the meanings of the English word “relaxation” is decreasing something. Because at the update stage of the shortest path you are essentially checking if you can decrease （optimize） the currently computed distance, that’s why it is called “relaxation condition”.

• Ex：
  
• 每个顶点最终的键值就是最短路径的权值。
• 可以将S与每次放入S的点之间的边用于生成最短路径树，从这个树的根节点到到每个叶结点走的路线就是所有的最短路径。

Dijkstra算法正确性

Dijkstra算法运行时间