给定一个图$G=?V,E?$，对于图中每条边$e=?i,j?$都有一个距离$d_{i,j}$。起始点是s，终点是t，问从s到t的最短路径是多少？

1.动态规划

最短路径问题是一个多步决策问题，所以可以先考虑用动态规划来求解。如果我们用OPT(i,j)表示点i到点j的最短路径，如果图中存在负值的边、负值环路，就转移方程会出现类似陷入循环等问题，而且转移方程无法与明确的d(u,v)做关联。所以我们通过引入一个新变量k，使得OPT(i,j)变成OPT(i,j,k)（从i到j经过最多k条边的最短路径），因为起点是固定的，我们只用考虑终点即可，最终定义OPT(v,k)：从s到点v最多经过k条边的最短路径。由此我们可以得到转移方程如下：
$$OPT(v,k)=\min \{\begin{array}{l}OPT(v,k?1)\\ {\min }_{?u,v?\in E}\{OPT(u,k?1)+d_{u,v}\}\end{array}$$
我们要在最多经过k条边内到达v，有两种可能，一是直接最多经过k-1条边就可以到达；二是先经过最多k-1条边到达u，存在一条边从u到v，经过此边到达v(可能有多个u满足，取最小者)，二者取较小即OPT(v,k)。

这个是Bellman Ford算法，是一种求解单源最短路径的算法。

伪代码如下：

通过上面算法，我们可以算出s到v的最短路径为4,下面表格还可以继续延申（k最多可能为8）。

2.贪心算法

在有了动态规划算法之后，我们观察上图示例可以发现是存在冗余计算的。

优化1：去除冗余计算

这个表格里的值的计算，要么是走了k-1条边后再走一条边从而让路径更短，要么是走k-1条边就能到，再多走一条边，路径也没有更短。后者这种在表格里就是横着平移，有很多重复的值是不需要计算的，为了找到什么时候可以不再继续计算该点的最小值（即该点不可能再被更新地更小了）。为此，我们定义一个特殊点$v^{?}$。如下
$$OPT(v^{?},k?1)=mi{n}_{v}OPT(v,k?1)$$
即在最多k-1条边那列中，OPT值最小的点（s点除外），我们将每一轮k对应的$v^{?}$添加到一个集合S中，添加后意味着OPT值在后续不会再发生变化，也就没有计算的必要了。

证明：本列最小OPT点无需再计算
由上面的定义，有$v^{?}$的转移方程如下：
$$OPT(v^{?},k)=\min \{\begin{array}{l}OPT(v^{?},k?1);(1)\\ {\min }_{?u,v^{?}?\in E}\{OPT(u,k?1)+d_{u,v^{?}}\};(2)\end{array}$$
必然有(2)>(1)，因为$OPT(u,k?1)\ge OPT(v^{?},k?1)$且$d_{u,v^{?}}\ge 0$，也就是一列的OPT最小值再经过多一条边肯定比不经过要大。所以
$$OPT(v^{?},k)=OPT(v^{?},k?1)$$

我们得到了第一个优化结论：
对于最多利用k-1条边走到v的最近点（即表中每列OPT值最小的点），它以后的OPT值不会再变化。

初始化一个集合S={s}，每次找出那一列的最小值的点，就把其添加进S，之后就不用算了，也就是下图绿色的是不需要计算的。

伪代码如下：

优化2：只考虑相邻最近点

前面我们已经加入了贪婪规则：一旦算出该点的最短距离后不再冗余计算该点OPT，但我们仍然需要遍历所有没加入集合S中点。其实每次我们只是多看一步，有很多相隔几步的点是不需要计算的，比如y与t离s比较远、不相邻，在k=1的时候应该不需要计算OPT(y,1),OPT(t,1)（注意这里的远是指离已遍历点远），同样地，在k=2时，已遍历集合中多了u，此时y离已遍历集合近了，但t仍然离S={s,u}远（不相邻）。

举个例子：
当k=1时，S={s},其更新了u,v.x三个点（它们与s相邻，一步可达），而y，t与s不相邻，因此没必要对y，t做计算。
当k=2时，S={s,u}，其更新了v,x,y（相邻），但t不相邻，虽然t被更新到了5，但是这个数字更不更新对最终结果并没有影响
当k=3时，S={s,u,v,x}，其更新了y,t（相邻），发现此时t被更新了，但它的更新来源于x，与之前的5没有关系（5换成无穷也是一样结果）

由此，我们知道，那些与已遍历集合S不相邻的点无需计算。
再进一步，那些相邻的点我们是否全部需要计算？

记d(v)表示从s到v的最短距离，设$u^{?}$是所有未遍历相邻点中离已遍历点最近的点，也即$d(u^{?})=mi{n}_{w\in S}d(w)+d(w,u)$。那么路径$P:s\to ...\to w\to u^{?}$是s到$u^{?}$的最短路径，路径长度为$d(u^{?})$。

举个例子：已遍历集合为{s,x,w}，相邻未遍历集合点(也可称一步到达点)为{$y,u^{?}$}，不相邻未遍历点为z（不用计算），对于已遍历点，我们知道d(x)=1,d(w)=2,而d(x)+d(x,y)=4，d(w)+d(w,u?)=3，所以3是s到$u^{?}$的最短路径长度。也就是$u^{?}$的最短路径不会再发生变化。

为什么$u^{?}$的最短距离不再变化?用反证法就可证明，假设存在另一个条路径$P\prime :s\to ...\to x\to y\to ...\to u^{?}$要更短，即$u^{?}$不通过w直达，则一定有$\mid P\prime \mid \ge d(s,x)+d(x,y)\ge d(w)+d(w,u^{?})=d(u^{?})$，矛盾。

由此，我们可以得出第二个优化结论
与已遍历点集合S相邻的最近点$u^{?}$ ，其到S的最短距离可以确定了。

这里的最近不要理解为$d(v,u^{?})$最小，应该是$d(v)+d(v,u^{?})$

这就是Dijkstra算法

L7：每一列找最小的d(v)
L8：把其加入S
L9-11:从S多走1步看能否刷新s->v的最短距离

特殊case：所有点之间的距离都为1，就变成了BFS广度优先搜索

经过以上两点优化，我们已经将Bellman Ford算法优化为Dijkstra算法。上面的优化就是贪心的思想，不考虑远的点，就只计算最近的相邻点，这就是一种局部最优的思想，所以Dijkstra 算法也属于贪心算法。