无边权

BFS

有边权

全源最短路

Floyd 算法（时间复杂度：O（））

1
2
3
4
5
6
7
void floyd(){
    for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++) 
    for (int j = 0; j < n; j++)                 
        if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) 
            dist[i][j] = dist[i][k] + dist[k][j];
}

单源最短路径

Dijkstra算法

朴素（时间复杂度：O（））
1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto Dijkstra = [&]() -> void{
   dist[s] = 0;
   int cur = s;
   while (!vis[cur]){
      vis[cur] = 1;
      for (auto it : e[cur])
         if (!vis[it.first] && dist[it.first] > dist[cur] + it.second)
              dist[it.first] = dist[cur] + it.second;
              int mini = INF;
              for (int i = 1; i <= n;i++)
                 if (!vis[i] && dist[i] < mini)
                    mini = dist[i], cur = i;
    }
 };
堆优化（时间复杂度：O（ ））
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
auto Dijkstra = [&]() -> void{
    for(int i=1;i<=n;i++)
        dist[i] = inf;
    dist[s] = 0;
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({0,s});
    while (!q.empty()){
        auto [dis,u] = q.top();
        q.pop();
        if(dis > dist[u])continue;
        for (auto &[x,y]: e[u])
            if (dist[x] > dist[u] + y){
                dist[x] = dist[u] + y;
                q.push({dist[x],x});
            }   
    }
};