Dijkstra

知识梗概

模板

//g[N][N]:图邻接矩阵  dist[V]:起点到每一个点的最小距离  st[N]=true:该点当前存储的已经是最短路径
//初始化为极大值:0x3f3f3f3f

int g[N][N],dist[V];
bool st[N];

int Dijkstra(){
    //n个点循环n次
    for(n){
        //在还没有确定最短路径的点中，找到dist值最小的点t
        //st[t]=true
        //用这个点t来更新与之相关的点的dist
    }

}

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;

const int N=510;
int g[N][N],dist[N];
bool st[N];

int n,m;

int Dijkstra(){
    memset(dist,0x3f,sizeof dist);  //初始化为无穷大
    dist[1]=0;   //初始点赋值
    for(int i=0;i<n;i++){  //遍历每一个点
        int t=n+1;
        //找到找到dist值最小的点t
        for(int j=1;j<=n;j++){
            if(dist[j]<dist[t]&&!st[j]) t=j;
        }

        //将其设置为true
        st[t]=true;

        //更新与之相关的点的dist
        for(int j=1;j<=n;j++){
            if(g[t][j]+dist[t]<dist[j]) dist[j]=g[t][j]+dist[t];
        }
    }

    //不连通
    if(dist[n]==0x3f3f3f3f) return -1;

    return dist[n];
}


int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);
    }
    cout<<Dijkstra();


    return 0;
}