图论复习(最短路)

前言

​ 下学期开始讲数据结构，我自己比较想去争取一下免修。不过其实关于图论的部分基本上已经是忘得差不多了（我觉得我现在可能唯一还会的算法就是倍增求$LCA$了）。图论的部分就打算从最简单的最短路和最小生成树开始复习了（据说下学期数据结构的内容要求只有$Dijkstra$算法）。

Dijkstra

​ 它中间的k很容易打漏

​ 应该是一个荷兰人在上世纪五十年代提出来的算法吧（记不清了），用来计算非负权图的单源最短路

算法思路

​ 假设起点为$S$,$dist[i]$表示从$S$到点$i$的最短路，$vis[i]$表示是否选中了这一个点($0$表示还没有选中，$1$表示已经选中)

​ 思路如下：

• $dist$数组初始化为$inf$,$dist[S]=0$，$vis$数组初始化为$0$
• 重复接下来的操作$n$次（假如这个图联通的话）
  • 从没有选中的点中选择$dist$值最小的一个点$u$,$vis[u]=1$
  • 设$v$是$u$可以直接到达的节点，$val$是这两条边的权值,$dist[v]=min(dist[v],dist[u]+val)$
• 或者说（不知道这个图到底联不联通）:
  • 每次选的点加入集合，每次从集合中去出点来，直到集合为空为止

算法的正确性

​ 我就根据自己的理解给一个证明了。不保证正确性。

​ 每一次都是从没有选择的一群点中选择$dist$最小的点$u$。首先就是不可能存在路径$S \rightarrow mid\rightarrow u $，$mid$属于还没有选择的点当中，十的$dist$更小。这是因为这个图是没有负权的，其他的点$dist$都是更大的，这样转移过来$u$的$dist$不会更小了。所以说每次选的点的最短路长度都是求出来了的，所有的点选完了那么最短路就求出来了

算法的优化

​ 暴力遍历数组选择节点时间复杂度为$O(n^2)$,为了优化算法，应当考虑提高选择结点的时候的效率。

​ 考虑用优先队列进行优化，将选择节点的效率提高到$O(\log n)$,这样算法的效率就提高了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

priority_queue< pair<int,int> >Que;
void Dijsktra(){
    clr(dist,0x3f);
    dist[S]=0;
    Que.push(make_pair(0,S));
    while(Que.size()){
        int u=Que.top().second;Que.pop();
        if(inq[u])continue;
        inq[u]=true;
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            int w=val[i];
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                Que.push(make_pair(-dist[v],v));
            }
        }
    }
}

上面是一份代码的案例。有自己define的语句。

Floyd

相当简单直白的算法了。边的权值可以负可以正，无向有向均可，但是要没有负环。

算法思路

​ 点$u$到点$v$的路径可以分分解为点$u$到点$mid$再到点$v$两条路径长度之和，所以说对于任意两个点之间的最短路，都枚举一下两个点之间转移的中间节点是多少就好了。

1
2
3
4

for(int k=1;k<=N;k++)//枚举中间节点
    for(int i=1;i<=N;i++)//枚举起点
        for(int j=1;j<=N;j++)//枚举终点
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

​ 缺点就是比较慢，时间复杂度达到了$O(n^3)$,优点是求得多源点最短路。

Bellman-Ford

相比于$Dijkstra$，可以处理有负边权的情况

算法思路

假设$dist[i]$表示从$S$到点$i$的最短路，$edge$是边的结构体,其中包含两个点和对应的权值

• $dist$数组初始化为$inf$,$dist[S]=0$
• 下面操作（松弛操作）重复$n-1$次：
  • 枚举每一条边，$dist[edge[k].u]=min(dist[edge[k].u],dist[edge[k].v]+edge[k].val)$
• 再进行一次松弛操作，如果说松弛操作可以成功，那么就说明这个图存在负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

bool Bellman_ford(){
	memset(dist,0x3f,sizeof(dist));
    dist[S]=0;
    for(int i=1;i<N;i++){
        for(int j=1;j<=E;j++){
			int u=edge[j].u;
            int v=edge[j].v;
            int w=edge[j].w;
            dist[u]=min(dist[u],dist[v]+w);
        }
    }
    for(int i=1;i<=E;i++){
        int u=edge[j].u;
        int v=edge[j].v;
        int w=edge[j].w;
        if(dist[u]>dist[u]+dist[v]+w)return false;
    }
    return true;
}

算法的正确性

​ 图的最短路不会包含正权的环（假设说有正环，那么肯定是有一条边可以删掉的，建议自己画图理解一下），也不会有负环（有负环哪来的最短路）。所以说一个图的最短路最多会有$N-1$条边。

​ $N$个点，$N-1$条边，其实就是一棵树，$Bellman-Ford$可以看作是以$S$作为根，一层一层地生成这棵最短路的树的一个过程，这棵树最多有$N-1$层，所以说最多只需要进行$N-1$次操作就好了，如果说还能继续的话就说明是存在负环了。

SPFA

算法思想

​ 相当于是通过队列的方式对$Bellman-Ford$进行优化。通过队列的方式减少了多余的扫描

• $dist$初始化为无穷大，$inq$初始化为0（用来记录是否在队列里面），$dist[S]$设为$0$，$inq[S]=1$并且放入队列当中
• 只要队列不为空：
  • 拿出队首的元素$u$，扫描队首元素可以到达的节点$v$
  • 如果说$dist[v]>dist[u]+w$,更改值，检查$v$是否在队列当中，如果说不在队列里面的话，那么放入队列里面,$inq$设置为$1$
  • 如果说一个点加入队列的次数超过了$N$说明有负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void SPFA(){
    //没有对于负环的检测
    memset(dist,0x3f,sizeof(dist));
    memset(inq,0,sizeof(inq));
    dist[S]=0;
    inq[S]=1;
    Que.push(S);
    while(Que.size()){
        int u=Que.front();Que.pop();
        inq[u]=0;
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            int w=val[i];
            if(dist[u]>dist[v]+w){
                dist[u]=dist[v]+w;
                if(!inq[v]){Que.push(v);inq[v]=1;}
            }
        }
    }
}