【图论】单源最短路问题

Dijkstra算法 -- 这是我职业生涯中唯一一个会写，却叫不上名字的算法

Dijkstra算法是一种单源最短路径算法，用于找出图中从一个源点到其他所有点的最短路径。该算法的原理是采用贪心策略，每次将距离源点最近的点加入到已确定最短路径的集合中，并更新其它节点的距离。具体实现过程如下：

1. 初始化距离数组dist[]，源点距离为0，其余点距离为无穷大。

2. 将所有点加入到未确定最短路径的集合中。

3. 在未确定最短路径的集合中找出距离源点最近的节点v，并将其加入到已确定最短路径的集合中。

4. 对节点v的所有邻居节点u进行更新，如果dist[u] > dist[v] + w(v,u)，则更新dist[u] = dist[v] + w(v,u)，其中w(v,u)是v到u的边权值。

5. 重复步骤3和4，直到所有节点都被加入到已确定最短路径的集合中。

Dijkstra算法的时间复杂度为O(V^2)，其中V为节点数。如果使用优先队列来优化实现，时间复杂度可以优化到O(ElogV)，其中E为边数。

relax -- 松弛操作

松弛操作是指在图论中，对某个节点的估计值进行更新的过程。通常用于单源最短路径算法，例如Dijkstra算法和Bellman-Ford算法中。具体来说，当我们使用Dijkstra算法或Bellman-Ford算法计算从源节点到其他节点的最短路径时，我们维护一个估计值列表，表示从源节点到每个节点的距离估计，随着算法的执行，我们逐步更新这个列表，直到找到最短路径。

对于Dijkstra算法，我们通过选择距离源节点最近的未标记节点来进行松弛操作，并更新源节点到该节点的距离估计值。以节点u为例，假设当前我们已经确定从源节点到节点u的距离估计值为d[u]，而节点u有一个邻居节点v，且u和v之间有一条边e(u,v)，边e(u,v)的权重为w(u,v)，我们可以通过以下方式来更新v的距离估计值：

d[v] = min(d[v], d[u] + w(u,v))

其中，min表示取两个值的较小值，即如果u到v的距离比当前估计值更短，则更新d[v]为新的估计值。

对于Bellman-Ford算法，我们对所有的边进行松弛操作，直到不能再进行更新为止。以边e(u,v)为例，我们可以通过以下方式来更新v的距离估计值：

if d[u] + w(u,v) < d[v]:
    d[v] = d[u] + w(u,v)

其中，if语句的意思是，如果u到v的距离比当前估计值更短，则更新d[v]为新的估计值。

需要注意的是，Bellman-Ford算法可以处理负权边，而Dijkstra算法只适用于图中没有负权边的情况。