它解决了什么问题

在大多数最短路径问题中，Dijkstra算法是最常用的、效率最高的。它是一种“单源”最短路径的算法，一次计算能够得到从一个起点到其他所有点的最短距离长度、最短路径的途径点

输入为带权图G=(V,E),边权非负(有负权边考虑Bellman-Ford/SPFA/Johnson)，给定起点，适用于有向图和无向图(无向图就加双向边)

核心思想(贪心+松弛)

维护每个点的“目前已知最短距离”dist[],反复从未确定的点里选出dist最小者u(用最小堆加速)，将它永久确定;然后用u去尝试”放松”所有出边(u,v,w):
如果dist[v]>dist[u]+w，就更新之，并记录parent[v]=u以便还原路径

因为所有边权非负，当前dist最小的未确定点u再走任何边其代价只会增加，不可能通过未确定的其他点得到更短的代替路径，故一旦选出就最优(贪心选择性质)

实现细节(邻接表+最小堆)

  • 数据结构:adj[u]存(v,w),priority_queue堆按(dist,node)升序
  • 常量:INF取很大(如4e18),避免溢出
  • 复杂度:用二叉堆:O((V+E)logV)O((V+E)logV)、用Fibonacci堆(理论):O(E+VlogV)O(E+VlogV)、稠密图用邻接矩阵+线性扫描:O(V2)O(V^2)更简单

步骤示例

步骤 做法 具体操作 结果
1 从起点s出发，用BFS扩展它的邻居节点 把这些邻居点放到一个集合A中，并记录这些点到s的距离
2 选择距离s最近的邻居v，继续用BFS扩展v的邻居 1. 在A中找到距离s最小的点v，把v的邻居点放到A中 2. 如果v的邻居经过v中转，到s的距离更短，则更新这些邻居到s的距离 3.从集合A中移走v，后面不再处理v 1.得到了从s到v的最短路径 2.v的邻居更新了到s的距离
3 重复步骤2，直到所有点都扩展到并计算完毕 集合A为空，计算出所有点到s的最短距离

C++模板(邻接表+最小堆，含路径还原)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;

struct Edge{
    int to;
    long long w;
};
const long long INF=(long long)4e18

int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int n,m,s;//顶点数n，边数m，起点s
    if(!(cin>>n>>m>>s))return 0;
    vector<vector<Edge>>adj(n+1);
    for(int i=0;i<m;++i){
        int u,v;
        long long w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});//无向图则再adj[v].push_back({u,w});
    }
    vector<long long>dist(n+1,INF);
    vector<int>parent(n+1,-1);
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;

    dist[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        auto [du,u]=pq.top();pq.pop();
        if(du!=dist[u])continue;
        for(auto &e:adj[u]){
            int v=e.to;long long nd=du+e.w;
            if(nd<dist[v]){
                dist[v]=nd;
                parent[v]=u;
                pq.push({nd.v});
            }
        }
    }

    //输出距离 不可达为-1
    for(int v=1;v<=n;v++{
        cout<<(dist[v]>=INF/2?-1:dist[v])<<(v==n?'\n':' ');
    })

    //还原s->t的路径
    int t=n;
    if(dist[t]>=INF/2){
        cerr<<"No path\n";
    }else{
        vector<int>path;
        for(int cur=t;cur!=-1;cur=parent[cur])
            path.push_back(cur);
        reverse(path.begin(),path.end());
        cerr<<"Path:";
        for(int x:path)cerr<<' '<<x;
        cerr<<"\n";
    }
    return 0;
}

用long long存边权与距离;du!=dist[u]过滤过期项
多组数据时记得清空容器与重置dist/Parent
无向图要加双向边，有多条边时正常处理(选择更优)

Go模板(最小堆+路径还原)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package main
import(
    "fmt"
    "container/heap"
    "bufio"
    "os"
)

type Edge struct{
    to int
    w int64
}
const INF int64=4e18

type Item struct{
    d int64 
    v int
}
type MinHeap []Item

func (h MinHeap) Len() int{
    return len(h)
}
func (h MinHeap) Less(i,j int) bool{
    return h[i].d<h[j].d
}
func (h MinHeap) Swap(i,j int){
    h[i],h[j]=h[j],h[i]
}
func (h MinHeap) Push(x interface{}){
    *h=append(*h,x.(Item))
}
func (h MinHeap) Pop() interface{}{
    old:=*h
    x:=old[len(old)-1]
    *h=old[:len(old)-1]
    return x
}

func main(){
    in:=bufio.NewReader(os.Stdin)
    out:=bufio.NewReader(os.Stdout)
    defer out.Flush()

    var n,m,s int
    if _,err:=fmt.Fscan(in,&n,&m,&s);err!=nil{
        return
    }

    adj:=make([][]Edge,n+1)
    for i:=0;i<m;i++{
        var u,v int
        var w int64
        fmt.Fscan(in,&u,&v,&w)
        adj[u]=append(adj[u],Edge{v,w})
        //无向图:adj[v]=append(adj[v],Edge{u,w})
    }

    dist:=make([]int64,n+1)
    parent:=make([]int,n+1)
    for i:=1;i<=n;i++{
        dist[i]=INF
        parent[i]=-1
    }
    dist[s]=0

    h:=&MinHeap{}
    heap.Init(h)
    heap.Push(h,Item{0,s})

    for h.Len()>0{
        it:=heap.Pop(h).(Item)
        du,u:=it.d,it.v
        if du!=dist[u]{//过期项
            continue
        }
        for _,e:=range adj[u]{
            v:=e.to
            nd:=du+e.w
            if nd<dist[v]{
                dist[v]=nd
                parent[v]=u
                heap.Push(h,Item{nd,v})
            }
        }
    }

    for v:=1;v<=n;v++{
        if dist[v]>INF/2{
            fmt.FPrint(out,-1)
        }else{
            fmt.Fprint(out,dist[v])
        }
        if v<n{
            fmt.Fprint(out," ")
        }
    }
    fmt.Fprint(out)

    //还原路径
    if dist[n]<INF/2{
        path:=[]int{}
        for cur:=n;cur!=-1:cur=parent[cur]{
            path=append(path,cur)
        }
        //反转
        for i,j:=0,len(path)-1;i<j;i,j=i+1,j-1{
            path[i],path[j]=path[j],path[i]
        }
        //打印到标准错误 避免干扰测评输出
        fmt.Fprint(os.Stderr,"Path:")
        for _,x:=range path{
            fmt.Fprint(os.Stderr," ",x)
        }
        fmt.Fprintln(os.Stderr)
    }
}

稠密图的O(n2n^2)写法

适合E≈V2E \approx V^2

  1. dist[s]=0，其余INF全false

  2. 循环n次：

    • 在线性扫描访问点中找dist最小的u，标记vis[u]=true
    • 用u松弛所有v:dist[v]=min(dist[v],dist[u]+w[u][v])复杂度O(n2)O(n^2)

常见坑

  • 负权/负环：dijkstra不适用，哪怕只有一条负边也不行
  • 整型溢出:总全值可能很大，统一用64位整型
  • 多组数据：注意初始化
  • 不可达：输出-1等条件
  • 双向边别忘了加两次：并行多边/自环无序特判，不会影响正确性

进阶与变体

  • 0-1 BFS：边权只取0/1，用双端队列O(V+E)O(V+E)
  • Dial’s Algorithm:非负小整数权(最大权C不大)可用桶实现O(V+E+VC)O(V+E+VC)
  • 多源最短路:把所有源点dist=0同时入堆
  • A*：有启发式的单源单目标更快，需要一致，可采纳的启发函数
  • K次最短路：在Dijkstra框架上记录到达次数