用 Dijkstra 算法解决最短路问题

话不多说，先看图

1.1 朴素版的Dijkstra算法

一般用到这个情况稠密图，也就是节点的个数比边的个数少。 （稠密图用邻接矩阵存储）

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];//稠密图用邻接矩阵，g[a][b] 表示从a点到b点的距离
int dist[N];//用于存储每个店到起点的最小距离
bool st[N];//用于在更新最短距离时，判断当前点的最短距离是否确定，是否需要更新

int dijkstra(){
    
    memset(dist, 0x3f, sizeof dist);//初始化距离， 0x3f代表无限大
    dist[1] = 0;//第一个点到自身的距离时0
    
    for(int i = 0; i < n; i++){//有n个点需要进行n次迭代
    
        int t = -1;    //t存储当前访问的点
        
        for(int j=1; j<=n; j++)  //这里的 j 代表从1号点开始
            if(!st[j] && (t == -1 || dist[t] > dist[j]))   //寻找未确定最短路径的点钟距离最短的点
                t = j;
        
        for(int j = 1; j<=n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
            
        st[t] = true;
        
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    scanf("%d%d", &n, &m);
    
    memset(g, 0x3f, sizeof g);//初始化距离
    
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        
        g[a][b] = min(g[a][b], c);//和之前a点到b点的最小距离进行比较，取两个中的最小值
    }
    
    printf("%d\n", dijkstra());
    
    return 0;
}

2.2 堆优化版的Dijkstra算法

用到这种情况的是稀疏图。 （点多边的数目少）

思路：

以 1 号点为例，判断一下1号点到源点的最短距离是不是已经确定了， 如果已经确定了， 跳出本次循环。如果还没有确定，厕把他的 st[1] = true , 这里思考一下我们为什么把1号点的状态改为 true, 因为所有指向1 号点的点最短距离已经确定， 自然 1 号点的最短距离也就确定了， 接下来遍历一下1号点所有指向的点 更新 1 号点指向的点的最短距离 ，

#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);  初始化所有点到源点的距离为 无穷大
    dist[1] = 0;  //  1 号点就是源点， 所有到自身的距离是 0
    priority_queue<PII, vector<PII>, greater<PII>> heap; //小根堆
    heap.push({0, 1});  // 距离源点最近的点入堆
    
    while(heap.size()) // 堆不空
    {
        auto t = heap.top();
        heap.pop();
        
        int var = t.second;  //取到 还没有确定到源点的最短距离的点中 到源点距离最近的点
        
        if(st[var]) continue; //判断一下该点到源点的距离是否已经确定， 如果确定跳出本次循环
        st[var] = true;
        
        for(int i = h[var]; i != -1; i = ne[i])//遍历一下var 所有指向的点
        {
            int j = e[i];
            if(dist[j] > dist[var] + w[i])
            {
                dist[j] = dist[var] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    printf("%d\n", dijkstra());
    
    return 0;
}