数据结构算法笔记#3.4:最短路径

从一个点走到另一个点，最短需要走多远的长度？

这是一个经典的最短路径问题，有很多种方法可以解决它。

而在这其中，有两种算法最为经典：一种名为Dijkstra算法，另一种，名叫Floyd算法。

Dijkstra

算法简介

Dijkstra算法主要是用来计算单源点到其余各点的最短距离，其基本思想和之前的Prim类似，都运用了加点+贪心 的做法，整体的流程也十分类似。

先从最开始确定的起点u开始，其余各点与它的距离即为邻接矩阵中各点到它的距离（也有可能没有邻接关系，距离为无穷）。然后在这些点中找到距离起点u最近的一个，接着通过这个点对所有点进行“ 松弛 ”操作。所谓“松弛”，即对于一段路径<i,j>，找到一个点k，使得<i,k>+<k,j>的长度小于<i,j>的长度。要找到两个点之间的最短路长度，就需要这样不断地松弛。直到将所有点尝试一遍，便能找出起点到其余各点的最短值。

这虽然只是简单的贪心思想，但其正确性已被数学方法所证明，有兴趣的可以自行了解，这里只大概介绍过程。

代码实现


#define MAX_WEIGHT 0x3fffffff
template <class T>
void AdjacencyMatrix<T>::dijkstra(int u)
{
    vector<int> spath(vertex_num, MAX_WEIGHT); //最短路径
    int curVex = -1;                           //当前顶点
    int minCost = MAX_WEIGHT;
    vector<int> visited(vertex_num, 0); //顶点是否被遍历过
    for (int i = 0; i < vertex_num; i++)
        spath[i] = adjacent[u][i]; //spath[]初始化为起点到每个点的距离,自身记为0
    spath[u] = 0;
    for (int i = 1; i < vertex_num; i++)
    {
        minCost = MAX_WEIGHT;
        for (int j = 0; j < vertex_num; j++) //找出距离起点最近的点
            if (!visited[j] && spath[j] < minCost) {
                minCost = spath[j];
                curVex = j;
            }
        visited[curVex] = 1;                 //将其记为已访问
        for (int j = 0; j < vertex_num; j++) //对其相邻点进行对起点的松弛,找到更短路径
            if ((adjacent[u][curVex] + adjacent[curVex][j] < spath[j]))
                spath[j] = adjacent[u][curVex] + adjacent[curVex][j];
    }
    /**/
    //输出结果
    /**/
}

首先要注意的是，由于我们的算法过程中有加法的操作，再用INT_MAX的话会使数值溢出，所以这里一般用0x3fffffff来作为无穷大。

关于邻接矩阵的定义在之前的文章里已经给过，此处就不多赘述。先定义几个变量：

vector<int> spath(vertex_num, MAX_WEIGHT); //最短路径
int curVex = -1;                           //当前顶点
int minCost = MAX_WEIGHT;
vector<int> visited(vertex_num, 0); //顶点是否被遍历过

spath[]数组用来记录起点到其余各点最短路径的长度，也就是存储最终结果的数组。curVex用来记录当前搜索到的距离起点最近的顶点。

在初始化数据之后，即开始进行n-1次搜索，每次搜索都找出一个距离起点最近且未搜索过的点：

minCost = MAX_WEIGHT;
for (int j = 0; j < vertex_num; j++) //找出距离起点最近的点
    if (!visited[j] && spath[j] < minCost)
        curVex = j;
visited[curVex] = 1; //将其记为已访问

接着便是算法的核心，进行“松弛”操作：

1
2
3

for (int j = 0; j < vertex_num; j++) //对其相邻点进行对起点的松弛,找到更短路径
    if ((adjacent[u][curVex] + adjacent[curVex][j] < spath[j]))
        spath[j] = adjacent[u][curVex] + adjacent[curVex][j];

等到所有点都被搜索一遍，起点到各顶点的最短距离也被计算出来了。

Floyd

算法简介

Floyd算法也是用来求两点间最短路径的，但与Dijkstra算法不同，Floyd算法能一次性将图中任意两点间 的最短距离计算出来，并且实现起来十分简洁。

还记得上文中提到的“ 松弛 ”操作吗？要找到 i→j 的最短路，只需要分别用其它各个点作为中继，尝试出更短路径，Floyd算法的思想便于此类似：

要找到 i→j 的最短路，我们就先从顶点 a 开始尝试，看看 i→a + a→j 是否会更短。接着再多加一个顶点 b ，看看通过 a 与 b 进行中转会不会有更多距离。然后是 a, b 与 c ……以此类推，直到尝试完所有顶点的中转。此时得到的最短路径即为 i→j 的最短路。

代码实现

1	vector<vector<int>> spath = adjacent;

首先为了防止原矩阵被修改，我们创建一个原邻接矩阵的拷贝spath来存储信息。

接着一步步来，对于所有起点 i 与终点 j ，通过顶点 0 进行松弛：

for (int i = 0; i < vertex_num; i++)
   for (int j = 0; j < vertex_num; j++)
       if (spath[i][0] + spath[0][j] < spath[i][j])
           spath[i][j] = spath[i][0] + spath[0][j];

然后是顶点 1 ：

for (int i = 0; i < vertex_num; i++)
   for (int j = 0; j < vertex_num; j++)
       if (spath[i][1] + spath[1][j] < spath[i][j])
           spath[i][j] = spath[i][1] + spath[1][j];

由于最后要通过所有顶点都松弛一遍，所以显然，需要再嵌套一个循环：

for (int k = 0; k < vertex_num; k++)
    for (int i = 0; i < vertex_num; i++)
        for (int j = 0; j < vertex_num; j++)
            if (spath[i][k] + spath[k][j] < spath[i][j])
                spath[i][j] = spath[i][k] + spath[k][j];

Floyd算法到此结束。spath中存储的信息就是任意两点间的最短路径。

怎么样，是不是很简洁？下面是算法的完整代码：

template <class T>
void AdjacencyMatrix<T>::floyd()
{
    vector<vector<int>> spath = adjacent;
    for (int k = 0; k < vertex_num; k++)
        for (int i = 0; i < vertex_num; i++)
            for (int j = 0; j < vertex_num; j++)
                if (spath[i][k] + spath[k][j] < spath[i][j])
                    spath[i][j] = spath[i][k] + spath[k][j];
    /**/
    //输出结果
    /**/
}