【56. Dijkstra求最短路径】

思路

该题边比较多，属于稠密图，因此用邻接矩阵来存储边

• 除了存储图外我们还需要存储两个量

dist[n] //用于存储每个点到起点的最短距离
st[n]   //用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新

• 每次迭代的过程中我们都先找到当前未确定的最短距离的点中距离最短的点

int t=-1;       //将t设置为-1 因为Dijkstra算法适用于不存在负权边的图
for(int j=1;j<=n;j++)
{
    if(!st[j]&&(t==-1||dist[t]>dist[j])    //该步骤即寻找还未确定最短路的点中路径最短的点
        t=j;
}

• 通过上述操作当前我们的t代表就是剩余未确定最短路的点中 路径最短的点
  而与此同时该点的最短路径也已经确定我们将该点标记

st[t]=true;

• 然后用这个去更新其余未确定点的最短距离

for(int j=1;j<=n;j++)
    dist[j]=min(dist[j],dist[t]+g[t][j]);
//这里可能有同学要问j如果从1开始的话 会不会影响之前已经确定的点的最小距离
//但其实是不会 因为按照我们的Dijkstra算法的操作顺序 先确定最短距离的点的距离已经比后确定的要小 所以不会影响
//当然你也可以在循环判断条件里加上if(!st[i])
//这里j从1开始只是为了代码的简洁

举例

1. 用一个 dist 数组保存源点到其余各个节点的距离，dist[i] 表示源点到节点 i 的距离。初始时，dist 数组的各个元素为无穷大。
   用一个状态数组 state 记录是否找到了源点到该节点的最短距离，state[i] 如果为真，则表示找到了源点到节点 i 的最短距离，state[i] 如果为假，则表示源点到节点 i 的最短距离还没有找到。初始时，state 各个元素为假。
   
2. 源点到源点的距离为 0。即dist[1] = 0。
   
3. 遍历 dist 数组，找到一个节点，这个节点是：没有确定最短路径的节点中距离源点最近的点。假设该节点编号为 i。此时就找到了源点到该节点的最短距离，state[i] 置为 1。
   
4. 遍历 i 所有可以到达的节点 j，如果 dist[j] 大于 dist[i] 加上 i -> j 的距离，即 dist[j] > dist[i] + w[i][j]（w[i][j] 为 i -> j 的距离） ，则更新 dist[j] = dist[i] + w[i][j]。

5. 重复 3 4 步骤，直到所有节点的状态都被置为 1。

题目

代码

// 500个点，100000条边，因此用稠密图存储
//对于重边，只保留距离最短的边
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510;
int n, m;
int g[N][N];          //为稠密阵所以用邻接矩阵存储
int dist[N];          //从1号点，到每一个点的当前最短距离是多少
bool st[N];           //当前点的最短路是否确定


int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);   //将所有点初始化为正无穷
    dist[1] = 0;                       //1号点初始化为0
    
    //迭代n次，第一步先找最小值，找到当前没有确定最短路长度的点当中，距离最小的
    for (int i = 0; i < n; i ++)
    {
        int t = -1;                    //t存储当前访问的点
        for (int j = 1; j <= n; j ++)  //遍历所有的点
        if (!st[j] && (t == -1 || dist[t] > dist[j]))           //如果当前点没有确定最短路，或者当前t不是最短的
            t = j;
    
        st[t] = true;                                          //将t加入到集合中
        
        //依次更新每个点所到相邻的点路径值
        for (int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);          //用1到t的距离加上t到j这条边长度，来更新从1到j这条边
       
    }
    
    //如果第n个点路径为无穷大即不存在最低路径，代表1到n不连通，否则返回n的最短距离
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);         //初始化图 因为是求最短路径,所以每个点初始为无限大
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);      //如果发生重边的情况则保留最短的一条边
    }
    int t = dijkstra();
    
    cout << t;
    return 0;
}

一共有三个for循环

• 第一个是外层循环
  枚举选的次数， 因为最短的路径可能要走 n-1 步走到，每一次选内层中的一个点来走
  内层循环中，
• 第一个for ， 找到 从 1-> j 最近的一个点
  然后 利用这个点 ， 尝试 修改其他的路径
• 第二个for , 如果更短，就更新距离

注意

• 稠密图用邻接矩阵存储，稀疏图用邻接表存储

有向图与无向图区别

• 无向图是一种特殊的有向图
• 在最短路中，如果告诉是无向边的话，就直接连接俩条变就可以（一条a->b，一条b->a），因此只考虑有向图就可以（可以直接用有向图的算法，解决无向图的问题）

文章借鉴：https://www.acwing.com/solution/content/38318/