图论最短路算法笔记

1 图的基本操作

1.1 图的存储

图存储有两种方法：邻接表和邻接矩阵。

• 邻接表：

g[N][N] = {};
...
memset(g, 0x3f, sizeof g);
g[u][v] = w;

• 邻接矩阵：

int head[N] = {};
memset(head, 0x3f, sizeof head); 
struct edge{
    int pre, to, val;
}EDGE[N];
inline void addedge(int u, int v, int w, int i){
    EDGE[i] = {v, w, head[u]};
    head[u] = i;
}

1.2 图的遍历

图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次（访问一次，但不止用到一次）。 图的遍历操作和树的遍历操作功能相似。

2 最短路算法

图求最短路有算法：

• Floyd
• Dijkstra
• SPFA（死了）
• Bellman-Ford
• ...

2.1 Floyd

• 用途：求任意两个结点之间的最短路
• 复杂度：\(O(n^3)\)
• 适用：适用于任何图，不管有向无向，边权正负，但是最短路必须存在。

for(reg int k=1; k<=n; ++k)
    for(reg int i=1; i<=n; ++i)
        for(reg int j=1; j<=n; ++j)
            if(g[i][k] + g[k][j] < g[i][j])
                g[i][j] = g[i][k]+g[k][j];

以上：g 为邻接矩阵。

2.2 Dijkstra

• 用途：单源最短路径
• 复杂度：\(O(n^2)\) -> \(O(nlogn)\)
• 适用：非负权图

步骤

• 1 初始化：
  源点 \(u\)，dis[N]，book[N]。
  建立集合 \(S\) 与 \(V-S\)。刚开始，只有 \(u\) 在 \(S\) 中。

vector<edge> e[MAXN];
int dis[MAXN], book[MAXN];

• 2 找 dis[] 最小：
  开始，dis[n] 为 源点 \(u \rightarrow n\) 的特殊最短路。
  寻找 dis[n] 中最小的节点 \(t\)（可优化）。
  
  
• 3 加入集合 \(S\)
  加入集合 \(S\)，现在 \(S\) 表示为最短路的部分。
  
• 4 借东风
  与 Floyd 较为类似，就是以一个节点 \(i\) 作中转点，看看能不能将与周围的节点 \(k_1, k_2, ..., k_n\) 的边 \(k_1 \rightarrow i \rightarrow k_2\) 的长度减小（松弛）。
  
• 5 判结束
  如果 \(V-S\) 集合为空集，那么全部的 dis[] 都处理完毕，这时的 dis[n] 为 源点 \(u \rightarrow n\) 的最短路。
  

朴素算法（没写过，来自 oi-wiki）：

struct edge {
    int v, w;
};
vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
void dijkstra(int n, int s) {
    memset(dis, 0x3f, (n + 1) * sizeof(int));
    dis[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = 0, mind = 0x3f3f3f3f;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dis[j] < mind)
                u = j, mind = dis[j];
        vis[u] = true;
        for (auto ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) 
                dis[v] = dis[u] + w;
        }
    }
}

堆优化

堆优化就是用堆进行优化，而朴素的算法是“扫描”一遍图找最小的点。而小根堆优先队列优化就可以快速维护最小的点，大大减少时间复杂度（ \(O(nlogn)\) ）。

struct edge {
    int pre, to, val;
}EDGE[MAXN];
int dis[MAXN], book[MAXN], head[MAXN];

inline void addedge(int u, int v, int w, int i){
    EDGE[i] = {v, w, head[u]};
    head[u] = i;
}

inline void dijkstra(int s){
    memset(dis, inf, sizeof dis);
    priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;
    heap.push({0, s});
    while(!heap.empty()){
        int t = heap.top().second;
        heap.pop();
        if(book[t])
            continue;
        book[t] = true;
        for(reg int i=head[t]; i; i=EDGE[i].pre){
            if(dis[EDGE[i].to] > EDGE[i].val+dis[t]){
                dis[EDGE[i].to] = EDGE[i].to+dis[t];
                heap.push({dis[EDGE[i].to], EDGE[i].to});
            }
        }
    }
    return;
}