Dijkstra

非负权值单源最短路，Dijkstra算法，O(mlogm)

从未访问的点中选出一个距离源点最近的点，加入到已访问的点中，直到所有点都被访问过为止。

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
class Dijkstra{
private:
    struct edge{ ll v, w; };
    struct node{
        ll dis, u;
        bool operator>(const node &a) const { return dis > a.dis; }
    }; 
    vector<vector<edge>> G;
    vector<int> vis;
    vector<ll> dis;
    priority_queue<node,vector<node>,greater<node>> Q;
    ll n=0;
    //换源前初始化
    void Init(){
        while(!Q.empty()) Q.pop();
        FORLL(i,1,n){
            vis[i]=0;
            dis[i]=INF;
        }
    }
public:
    Dijkstra(ll _n):n(_n),G(_n+1),vis(_n+1,0),dis(_n+1,INF){}
    void addedge(ll u,ll v,ll w){//加边
        G[u].push_back({v,w});
    }
    //s为源点的单源最短路
    void solve(ll s){
        Init();
        dis[s] = 0;
        Q.push({0, s});
        while (!Q.empty()) {
            ll u = Q.top().u;
            Q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (auto e : G[u]) {
                ll v = e.v, w = e.w;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    Q.push({dis[v], v});
                }
            }
        }
    }
    //到t的最短路
    ll getdis(ll t){
        return dis[t];
    }
    //访问dis数组
    ll operator[](ll i){
        return dis[i];
    }
};

Floyd

适用于任何图，不管有向无向，边权正负，但是最短路必须存在（不能有负环）

复杂度比较高，但是常数小，容易实现

定义f[k][x][y]为从x到y，只能经过1~k的点的最短路，f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k] + f[k-1][k][y])

f[n][x][y]即为所求

代码略