5.7 最短路径

最短路径问题是图的一个比较典型的应用问题。例如，假设一个大学有 ​ n 个学院，有一张地图画出了 ​ n 个学院及学院相互之间连通的道路，道路上还标有相互之间的距离。那么能否找到从学院 ​ A 到学院 ​ B 之间一条距离最近的路径呢？如果将学院用点表示，学院之间的道路用边表示，学院间的距离作为边的权值，那么这个问题就可归结为在网图中，求顶点 ​ A 到顶点 ​ B 的所有路径中，边的权值之和最短的那一条路径。这条路径就是两点之间的最短路径，对于非网图，其最短路径是指两个顶点之间经历的边数最少的路径。我们称所求最短路径上的第一个顶点为 “源点”，最后一个顶点为 “终点”。

本节讨论如何找到这条最短路径的算法，考虑到道路交通图的有向性，我们将讨论带权有向图（有向网）。

5.7.1 单源最短路径

1. 算法思想

单源点路径问题是指，已知一个有向网 ​ G=(V, E) 和网中某个源点 ​ v \in V ，求从该源点到网中其他各个顶点之间的最短路径。怎样求得这些最短路径？1959 年迪杰斯特拉（Dijkstra）提出了最短路径的经典算法。该算法的基本思想是：

设置两个顶点集合 ​ S 和 ​ T ，集合 ​ S 中存放已找到最短路径的顶点，集合 ​ T 中存放当前还未找到最短路径的顶点。初始状态时，集合 ​ S 只包含源点，然后从集合 ​ T 中选择到源点路径最短的顶点 ​ v_i 加入 ​ S 中，并修改源点到集合 ​ T 中剩余顶点的最短路径值，集合 ​ T 中各顶点的新的最短路径长度值为原来的最短路径长度值与从源点过顶点 ​ v_i 到达该顶点的路径长度中的较小者。不断重复此过程，直到集合 ​ T 中的顶点全部加入集合 ​ S 中为止。

2. 算法举例

图 5.19 所示的有向网中，从源点 ​ v_1 到终点 ​ v_2 之间存在多条路径，如路径 ​ \{v_1, v_2\} 的长度为 6，路径 ​ \{v_1, v_3, v_2\} 的长度为 5，其中以路径 ​ \{v_1, v_3, v_2\} 的长度 5 为最短。类似地，从源点 ​ v_1 到其余各个顶点也都存在一条路径长度最短的路径，如下所列。

从源点 ​ v_1 到网中其余各终点的最短路径按路径长度从短到长依次为：

路径 ​ \{v_1, v_3\} 的路径长度为 3；

路径 ​ \{v_1, v_3, v_2\} 的路径长度为 5；

路径 ​ \{v_1, v_3, v_4\} 的路径长度为 6；

路径 ​ \{v_1, v_3, v_5\} 的路径长度为 7；

路径 ​ \{v_1, v_3, v_5, v_6\} 的路径长度为 8。

采用迪杰斯特拉算法来分析图 5.19 的最短路径，假设源点为 ​ v_1 ，​ v_1 到各顶点的最短路径的变化状况见表 5.2。

从以上求最短路径的过程可见，采用迪杰斯特拉算法类似于普里姆算法，需要保存当前已经求得的从源点 ​ v_1 到每个终点的最短路径。算法开始时先判断，如果从源点到各终点有一条直接弧相连，则从源点到该终点存在一条路径，其路径长度即为该弧上的权值，此权值也就是从源点到各终点的最短路径的初值；如果从源点到终点没有一条直接弧相连，那么从源点到该终点最短路径的初值设为 ​ \infty 。之后每求得一条源点到达某个终点 ​ v_i 的 “最短路径” 之后，就需要检查一下，是否存在经过这个顶点 ​ v_i 的其他路径（即是否存在从顶点 ​ v_i 出发的到达尚未求得最短路径的顶点的弧），如果存在，其长度是否比当前求得的路径长度短，如果是，则应修改当前路径。按照这样的方法，依次求出源点到每个顶点的最短路径。

3. 代码实现

#include<bits/stdc++.h>
using namespace std;

int dist[1001];//dist[i]表示起点到i号点所需的最小路径长
int vis[1001]={0}; //标记 s[i]表示第i号顶点已经走过了
int inf = INT_MAX;//无限长 即路径不可达
int g[1001][1001];//存储无向图
int m,n;//m表示有m条路径 n表示最大顶点编号

void dij(int st)//迪杰斯特拉算法
{
    int i,j,u,mindis=inf;
    for (i = 1; i<=n ;i++)
    {
        dist[i] = g[st][i];//初始化 从编号为1的点开始 到达其余点所需的长度
        vis[i] = 0;
    }
    vis[st] = 1;//把1号点(起点)标记为走过
    for (i = 1; i <= n ; i++ )
    {
        mindis = inf; //初始化当前最短路为无限大
        for (j = 1; j <= n; j++)//遍历所有顶点
        {
            if (vis[j] == 0 && dist[j] < mindis)//如果j号顶点还未被访问过 不断更新起点到达j号节点的最短路径（女朋友算法）
            {
                u = j;//u表示当前循环下 起点到达所有未被访问过的节点最短的点
                mindis = dist[j];//更新最短路径
            }
        }
        vis[u] = 1;//u号节点加集合（已访问）
        for (j = 1; j<=n ;j++)
        {
            if(vis[j]==0)//如果j号节点未被加入集合中（未标记）
            {
                //如果上一轮找到的u(即起点到已经访问过节点的最短路径节点)可以达到本轮的j号节点
                //并且 上一轮起点到达u号节点的路径+当前u号节点到j节点的距离 比上一轮到达j号节点的路径短 更新最短路径（女朋友算法）
                if (g[u][j] < inf && dist[u] + g[u][j] < dist[j])
                {
                    //更新最短路径（女朋友算法）
                    dist[j] = dist[u] + g[u][j];
                }
            }
        }
    }
}

int main()
{
    int a,b,c,i,j;int st;
    // memset(s,0,sizeof(s));//初始化所有节点未被访问
    cin >> n >> m;//输入
    cin >> st;//输入起点编号
    for (i = 1; i <=n ;i++)
    {
        for (j = 1;j<=n;j++)
        {
            g[i][j] = inf;//初始化所有节点不可达
        }
        g[i][i] = 0;//i到i(原地)路径为0
    }
    for (i = 1; i<=m; i++)
    {
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = c;//将路径加入矩阵
    }
    dij(st);//调用迪杰斯特拉算法
    if (dist[n] == inf) cout << -1 << endl;//如果n不可达 输出-1
    cout << dist[n] << endl;//否则输出n
    return 0;
}