什么是迪杰斯特拉？
迪杰斯特拉是图论中的一种算法，用于在有向图，且当每条边权重均非负且没有最大边要求时，求最短路径。

迪杰斯特拉的基本思想是用一个指针，依次从第一号点开始遍历，并且每次遍历过程均用该点来更新其余所有被该点相连的点，到起始处的距离。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
 
const int N = 510;
 
int g[N][N];//邻接矩阵可以看成二维数组，g[a][b]表示点a到点b的距离。
int n,m;//n个点，m条边。
 
int main(){
    
    cin >> n >> m;
    memset(g,0x3f,sizeof(g));
 
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;//输入a，b两个点,c为a，b距离。
        g[a][b] = min(g[a][b],c)//初始化。
    }
    return 0;
}

2.dijkstra算法实现：

int g[N][N];
int dis[N];
int n,m;
bool st[N];
 
int dijkstra(){
    memset(dis,0x3f,sizeof dis);
    dis[1] = 0;
    
    for(int i = 0;i < n-1;i++){
        int t = -1;//取未被标记最近点。
        
        for(int j = 1;j <= n;j++)
            if(!st[j] && (t == -1 || dis[t] > dis[j]))
            t = j;//指针未开始移动或者，此时点距起点距离更小，并且指针没移到过该点。
 
            for(int j = 1;j <= n;j++){
                dis[j] = min(dis[j],dis[t] + g[t][j]);//更新距离
            }
        
        st[t] = true;//标记
    }
    
    if(dis[n] == 0x3f3f3f3f)return -1;//如果值仍然是无穷则说明不存在最小值。或者1号点无法到达n号点。
    return dis[n];
}

完整代码：

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N = 510;
 
int g[N][N];
int dis[N];
int n,m;
bool st[N];
 
int dijkstra(){
    memset(dis,0x3f,sizeof dis);
    dis[1] = 0;
    
    for(int i = 0;i < n-1;i++){
        int t = -1;
        
        for(int j = 1;j <= n;j++)
            if(!st[j] && (t == -1 || dis[t] > dis[j]))
            t = j;
 
            for(int j = 1;j <= n;j++){
                dis[j] = min(dis[j],dis[t] + g[t][j]);
            }
        
        st[t] = true;
    }
    
    if(dis[n] == 0x3f3f3f3f)return -1;
    return dis[n];
}
 
int main(){
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> n >> m;
    memset(g,0x3f,sizeof g);
    
    while( m-- ){
        int x,y,z;
        
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y],z);
    }
    
    cout << dijkstra() << endl;
    
    return 0;
}

2.稠密型的dijkstra
当边数m  << 点数n^2时，用邻接表存。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
 
using namespace std;
 
const int N = 1e6 + 10;
typedef pair<int,int> PII;//first存距离，second存坐标
 
int n,m,h[N],e[N],ne[N],idx;
int dist[N],w[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;
    
    priority_queue<PII,vector<PII>,greater<PII>> heap;//定义小端堆
    heap.push({0,1});
    
    while(heap.size()){
        
        auto t = heap.top();//取最小值
        heap.pop();//去最小值
        
        int ver = t.second,distance = t.first;
        
        if(st[ver])continue;
        st[ver] = true;
        
        for(int i = h[ver];i != -1;i = ne[i]){
            int j = e[i];
            
            if(dist[j] > dist[ver] + w[i]){//更新
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f)return -1;
    return dist[n];
}
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> n >> m;
    memset(h,-1,sizeof(h));
    
    while(m--){
        int x,y,z;
        
        cin >> x >> y >> z;
        add(x,y,z);
    }
    
    cout << dijkstra() << endl;
    
    return 0;
}