最短路径问题的目的是找到从一个顶点到达另一个顶点的成本最小的路径。最短路径算法被广泛地应用于解决各种复杂的问题，比如在地图中寻找两个地点之间的最短路径，如何在网络连接中为路由器寻找最短的传输路径等等。为了实现最短路径算法，人们发明了一系列的算法，比如：Dijkstra算法与Bellman-Ford算法。但是这些算法都基于一个被称为放松的基本操作

在这篇文章中，我会详细介绍放松操作，同时给出解决最短路径问题的基本（通用）思想。

这篇文章的大纲是：

我们接下来要讨论的问题被称为单源最短路（Single-Source Shortest Path），通俗来讲，就是给定一幅加权图和一个特定的顶点s，称为源；我们的目标是对于图中任意一点v,计算从源s到达v的最短路径

G=(V,E)是一个加权图

目标：对于图中任意一点v,计算从源s到达v的最短路径

我们一起来看一个例子：

在这幅图中，我们取源s，对于顶点A，从s到达A的路径只有一条SA，所以最短路径就是SA，最小权重为1；对于顶点B,从s到达B的路径有两条：SB与SAB,显然最短路径是SAB,最小权重为1+1=2。

对于下面这幅图呢？

我们把最小权重写在每个顶点内部会得到图二，这就是我们的目标！

现在，我们就来一起看一下放松这一个最基本最重要的操作吧！