介绍

Dijkstra算法是一个单源最短路算法。

算法流程：

1.定义数组 $$???$$，代表到目前为止从起点到各个点的最短路径长度。初始时将 $$ ???_{s} $$ 设置为 0，其他点的设置为 $$+\infty$$。
2.从所有没有选择过的点中选择一个 $$???$$ 值最小的点，设为$$u$$。
3.对于从 $$?$$ 出发的每一条边 $$(?, ?, ?)$$，进行一次松弛操作。松弛指的是更新 $$???? = \min(????, ???? + ?)$$。
4.将点$$?$$标记为已经被选择过，回到步骤 2，直到不存在一条从已经选择过的点出发到达未选择过的点的边。

原版

#include<bits/stdc++.h>
using namespace std;

int mp[1000][1000]; // 存图
int dis[10000],vis[10000]; // 最短距离和是否访问过

void dijkstra(int n,int s){
    for(int i = 1;i <= n;i++)dis[i] = INT_MAX,vis[i] = false; // 初始全赋值为最大值，未经访问
    dis[s] = 0;// 起点距离为零
    while (1)
    {
        int u = 0,val = INT_MAX; // 从起点开始，寻找最小val
        for(int j = 1;j <= n;j++){
            if(!vis[j] && dis[j] < val)u = j,val = dis[j]; // 如果未访问且val小于最小val,更新u和val
        }

        if(u == 0)break;
        vis[u] = true; // 打标记
        for(int j = 0;j < 10000;j++)
            if(mp[u][j])dis[j] = min(dis[j],dis[u]+mp[u][j]);
    }

}

int main(){
    int n,m,s,u,v,w;
    cin>>n>>m>>s;
    for(int i = 0;i <= m;i++){
        cin>>u>>v>>w;
        mp[u][v] = w;

    }
    dijkstra(n,s);
    for(int i = 1;i <= n;i++)cout<<dis[i]<<" ";
}

时间复杂度：$$O(n^2)$$

优先队列优化

#include<bits/stdc++.h>
using namespace std;
const int maxn = 20005;
struct edge{
    int v,w;
};

struct node{ // 存储每个dis和对应的u
    int dis,u;
    bool operator<(const node &a)const {return dis > a.dis;}
};
vector<edge> e[maxn]; // 存边
int dis[maxn],vis[maxn]; // 距离和是否访问过
priority_queue<node> pq; // 存储dis的队列
void dijkstra(int n,int s){
    for(int i = 1;i <= n;i++) dis[i] = INT_MAX,vis[i] = false; // 初始化
    dis[s] = 0; // 起点距离为零
    pq.push((node){0,s}); // 起点加入队列
    while(!pq.empty()){ // 当队列不为空时
        int u = pq.top().u;pq.pop(); // 取出队首为u
        if(vis[u])continue; // 如u已被访问过则下一个
        vis[u] = true; // 打访问标记
        for(int j = 0;j < e[u].size();j++){
            edge ed = e[u][j];int v = ed.v,w = ed.w;
            if(dis[v] > dis[u] + w)dis[v] = dis[u] + w,pq.push((node){dis[v],v}); // 更新dis并加入队列
        }
    }
}

int main(){
    int n,m,s,u,v,w;
    cin>>n>>m>>s; // n 个点，m条边，起点为s
    for(int i = 0;i < m;i++){
        cin>>u>>v>>w; // 有边 u -> v ，价值w
        edge ed;
        ed.v = v;
        ed.w = w;
        e[u].push_back(ed); // 将边加入数组
    }
    dijkstra(n,s);
    for(int i = 1;i <= n;i++)cout<<dis[i]<<" "; // 输出
    return 0;
}

时间复杂度：$$ O(m\ log\ m) $$