算法板子-Dijkstra算法朴素版（带注释）

Dijkstra是一种基于贪心的单源最短路算法，本文记录其朴素版，时间复杂度为n的平方

• 需要的存储结构

const int N=600,INF=0x3f3f3f3f;
int n,m;
int d[N],path[N]; //d数组存储当前点到原点的最小距离，path存储最小路径情况下，当前点的上一个节点
int mp[N][N]; //邻接矩阵
bool book[N]={0};  //判断当前点存储的是否为最小权值（是否进行过贪心处理 or 是否遍历访问过）

• 初始化

void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            mp[i][j]=INF;  //将邻接矩阵权值置最大，方便后续贪心操作
        }
        d[i]=INF;//将d数组置最大，理由同上
        path[i]=-1;//-1状态表示当前点还未找到最小路径前驱
    }
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(x!=y){ //判自环
            mp[x][y]=min(mp[x][y],z); //判重边，有重边的情况下贪心的取最小即可
        }
    }
}

• Dijkstra算法本体

void Dijkstra(){
    d[1]=0;//初始时将点1作为原点，将其d数组置0（自身到自身距离为0）
    for(int i=1;i<=n;i++){
        int t=-1; //t代表当前情况下，与原点拥有最短路径的点
        for(int j=1;j<=n;j++){
            if((!book[j]&&t==-1)||(!book[j]&&d[j]<d[t])){
                t=j;
            }
        }//每次贪心的选取当前全图中最短的路径
        book[t]=1;
        for(int j=1;j<=n;j++){//贪心的制造每个点到原点的最短路径
            if(d[j]>mp[t][j]+d[t]){//如果当前原点到j的路径长度大于原点到t的距离加t到j的距离就贪心地选取最小的路径距离
                d[j]=mp[t][j]+d[t];
                path[j]=t;//记录j的前驱节点
            }
        }
    }
}

• 完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=600,INF=0x3f3f3f3f;
int n,m;
int d[N],path[N]; //d数组存储当前点到原点的最小距离，path存储最小路径情况下，当前点的上一个节点
int mp[N][N]; //邻接矩阵
bool book[N]={0};  //判断当前点存储的是否为最小权值（是否进行过贪心处理 or 是否遍历访问过）
void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            mp[i][j]=INF;  //将邻接矩阵权值置最大，方便后续贪心操作
        }
        d[i]=INF;//将d数组置最大，理由同上
        path[i]=-1;//-1状态表示当前点还未找到最小路径前驱
    }
    for(int i=0;i<m;i++){
        ll x,y,z;
        cin>>x>>y>>z;
        if(x!=y){ //判自环
            mp[x][y]=min(mp[x][y],z); //判重边，有重边的情况下贪心的取最小即可
        }
    }
}
void Dijkstra(){
    d[1]=0;//初始时将点1作为原点，将其d数组置0（自身到自身距离为0）
    for(int i=1;i<=n;i++){
        int t=-1; //t代表当前情况下，与原点拥有最短路径的点
        for(int j=1;j<=n;j++){
            if((!book[j]&&t==-1)||(!book[j]&&d[j]<d[t])){
                t=j;
            }
        }//每次贪心的选取当前全图中最短的路径
        book[t]=1;
        for(int j=1;j<=n;j++){//贪心的制造每个点到原点的最短路径
            if(d[j]>mp[t][j]+d[t]){//如果当前原点到j的路径长度大于原点到t的距离加t到j的距离就贪心地选取最小的路径距离
                d[j]=mp[t][j]+d[t];
                path[j]=t;//记录j的前驱节点
            }
        }
    }
}
int main(void){
    cin>>n>>m;
    init();
    Dijkstra();
    int k=n;
    while(k!=-1){//输出路径
        cout<<k<<' ';
        k=path[k];
    }
    cout<<endl;
    cout<<(d[n]==INF?-1:d[n]);//d[n]==INF说明没找到
}

• 本体样例题目背景来源

AcWing-849. Dijkstra求最短路 I