Dijkstra

• 单源最短路：起点到其余点的最短路

• 多源最短路：每一对顶点间的最短路

Dijkstra(单源最短路,无负环)

Dijkstra的本质为BFS+贪心

算法流程：设标记数组$S$作为点集(标记已确定最短路的点集)，源点到每个顶点的最短路长度$dis$(初始化为$+\infty$表示该点不可达)，路径数组$path$(存储其上一个来源顶点,初始化为$-1$表示无路径)

循环执行下列步骤，直到点集$S$中所有顶点全部被标记或者所有顶点的$dis$值都无法再更新:

1. 选取最小顶点(贪心):从点集$S$中找出未被标记且$dis$最小的顶点$work$(首次即为源点)
2. 松弛入度边(BFS扩散):考查顶点$work$(将其在$S$中标记)，访问与$work$直接邻接且先前未被考查所标记的顶点$new$，检查其是否能通过$work$作为其中转点而使其$dis$更短(松弛入度边)。设$work$与$new$间的权值为$w$，则$dis[new]=min(dis[new],dis[work]+w)$
3. 更新最短路径:若$dis[new]$被更新(入度边被松弛)，则将$path[new]$修改为$work$

注：

1. 一旦顶点被加入到已选点集$S$中，其将不再被考查，最短路长度$dis$将不再改变。因此，Dijkstra不能用于求解含有负权的图。
2. Dijkstra不能求最长路

朴素版Dijkstra($O(V^2)$)

using ll=long long;
const ll INF=__LONG_LONG_MAX__;
ll n,m,s;//点数,边数,源点
struct vertex{
    int e=-1;
}v[n];
struct edge{
    int f,t,w,n=-1;
}e[m];
vector<bool>S;//只定义已选集合即可
vector<ll>dis,path;
void dijkstra(){
    dis.resize(n,INF),path.resize(n,-1),S.resize(n);
    dis[s]=0;//源点到自己距离为0
    for(ll j=0;j<n;j++){//尽可能使未选点集添加到已选点集
        ll minn=INF,i=-1;
        for(ll k=0;k<n;k++){
            if(!S[k]&&dis[k]!=INF&&dis[k]<minn){//贪心,从未选点集中选最小的
                i=k;
                minn=dis[k];
            }
        }
        if(i==-1) break;//剩余点均不可达
        S[i]=1;//将最小点加入已选集合中
        for(ll work=v[i].e;work!=-1;work=e[work].n){//考查最小点,BFS扩散其邻接点
            if(!S[e[work].t]&&e[work].w!=INF&&dis[e[work].t]>dis[i]+e[work].w){//松弛入度边
                dis[e[work].t]=dis[i]+e[work].w;
                path[e[work].t]=i;
            }
        }
    }
}

堆优化的Dijkstra($O(V{\log }_{2}V)$)

堆优化的Dijkstra为BFS+优先队列，另设小根堆$Q$动态维护最小边。

using ll=long long;
using pll=pair<ll,ll>;//first存点 second存最短距离
const ll INF=__LONG_LONG_MAX__;
struct vertex{
    ll e=-1;
}v[MAXV];
struct edge{
    ll f,t,w,n=-1;
}e[MAXE];
ll n,m,s;//点数 边数 源点
vector<bool>S;
vector<ll>dis,path;
bool cmp(pll a,pll b){//小根堆比较函数
    return a.second>b.second;
}
priority_queue<pii,vector<pii>,bool(*)(pll,pll)>pq(cmp);//构造小根堆
void dijkstra(){
    S.resize(n),dis.resize(n,INF),path.resize(n,-1);
    dis[s]=0;
    pq.push(make_pair(s,dis[s]));
    while(pq.size()){
        if(S[pq.top().first]){
            pq.pop();
            continue;
        }
        S[pq.top().first]=1;
        for(ll work=v[pq.top().first].e;work!=-1;work=e[work].n){//考查work,BFS扩散其邻接点
            if(!S[e[work].t]&&e[work].w!=INF&&dis[e[work].t]>pq.top().second+e[work].w){//松弛入度边
                dis[e[work].t]=pq.top().second+e[work].w;
                path[e[work].t]=pq.top().first;
                pq.push(make_pair(e[work].t,dis[e[work].t]));
            }
        }
        pq.pop();
    }
}