C++图论（最短路）

作为CSP-J2019的菜鸡，
我只过了国一分数线5分（~~真的是险~~），
还是写一篇关于图论的文章（~~虽然自己也不怎么会~~），
毕竟教别人也有助于自己提升。
这是我的第一篇文章。
好了，二话不说下面开始正文：（最下方有源码，点击获取）

图的存储

对于一张有向图，我们一般有邻接矩阵和邻接表两种储存方式，对于无向图，可以把无向边看作两条方向相反的有向边，从而采取和有向图一样的存储方式。

邻接矩阵

用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。我们用A(i,j)来表示这个矩阵：

表示方法:
① 用邻接矩阵表示顶点间的相邻关系
② 用一个顺序表来存储顶点信息

不带权的图

设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
若A(i,j)=1，则表示从点i出发到点j为通路；
若A(i,j)=0，则表示从点i出发无法到达点j。

下面来看一个例子：

如图，这是一个有向图。从1号节点出发能到达3号和4号节点，则A(1,3)=1，A(1,4)=1，而从3号节点出发无法到达1号节点，所以A(3,1)=0。所以用邻接矩阵存储的图可转化为：

无向图的表示方法和有向图是一样的，参照上述方法即可。

带权图

带权图就是每条边上都有一个权值的图。和不带权的图差不多，只不过把不带权的图中的1换成权值，0一般换成INF来表示（~~走了就亏大了~~），这里就不多做赘述。

邻接矩阵的实现

邻接矩阵的实现很简单也很容易理解，只要一个二维数组就行了：

const int MAXN = 1005;
int f[MAXN][MAXN],n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
	int x,y;
	cin>>x>>y;
	f[x][y]=1;
	//如果是带权图，就新定义一个变量w，输入，再赋给f[x][y]；
        //如果是无向图，再给f[y][x]赋值即可。
    }
}

特点

无向图的邻接矩阵中的值是对称的，而有向图的邻接矩阵中的值不一定对称。邻接矩阵的优点很明显，它能直接查找起点到终点是否有边及其权值，但缺点也很明显，它的时间和空间复杂度都达到了O(n²)！！！对于一个节点数特别大的稀疏图来说，边数m是远小于n²的，用邻接矩阵就会产生非常多的浪费，所以大数据一般用接下来要讲的邻接表存储。

邻接表

邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。

邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。

但在这里我并不想介绍所有的邻接表（如有需要请参考邻接表详解），而只介绍其中一种：链式前向星。

链式前向星

前向星其实是一种边集数组，用来记录以某个点为起点的所有边的起点终点和权值。

代码的实现是这样的：

const int MAXN=20010;
int cnt,head[MAXN];
struct rec{
    int w,e,next;
}edge[MAXN];
void add(int u,int v,int w){
    edge[cnt].w=w;
    edge[cnt].e=v;    //edge[i]表示第i条边的终点 
    edge[cnt].next=head[u]; //head[i]表示以i为起点的最后一条边的储存位置 
    head[u]=++cnt;
}
int main(){
    int m,n;
    for(int i=0;i<m;i++){
	int u,v,w;
	cin>>u>>v>>w;
	add(u,v,w);
    }
}

链式前向星的遍历也有所不同：

//遍历以u为起点的所有边
for(int i=head[u];i;i=edge[i].next){
    int v=edge[i].e;
    int w=edge[i].w;
    //找到一条有向边（u，v）,权值为w
    //接下来写要执行的操作
}

特点

相对于邻接矩阵而言，它虽然不能直接查找起点到终点是否有边及其权值，但是它的时间和空间复杂度为O(n+m),一般情况下要远小于O(n²)，后面讲到的SPFA算法就将用到它。

最短路

Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。其状态转移方程为 f[i][j]=min(f[i][k]+f[k][j],f[i][j])

程序实现如下：

const int MAXN=1005;
int f[MAXN][MAXN],n,m;
int main(){
    memset(f,0x3f,sizeof(f));//f[i][j]初始化为INF,此路不通 
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i][i]=0;//点到自身的距离当然是0
    for(int i=1;i<=m;i++){
	int u,v,w;
	cin>>u>>v>>w;
	f[u][v]=min(f[u][v],w);//如果有重边就保留最小的权值 
    }
    for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
		f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    //对于每一对顶点i和j，看看是否存在一个顶点k使得从i到k再到j比已知的路径更短。如果是更新它。
}

因为Floyd算法采用松弛操作，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n³);空间复杂度:O(n²)。

Floyd算法针对的是多源最短路的问题，虽然后面要讲的Dijkstra等算法执行n次也能达到多源，但都不如Floyd来的简单。

点击此处练练手

Dijkstra算法

Dijkstra算法算是贪心思想实现的，解决的是单源最短路问题。首先把起点到所有点的距离存下来找个最短的，然后进行一次松弛操作再找出最短的距离。

这里讲的只是朴素的算法，没有优化。

程序实现如下：

const int MAXN=2005;
int d[MAXN],vis[MAXN],f[MAXN][MAXN];
int n,m,s;
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        f[u][v]=min(f[u][v],w);
    }
    memset(f,0x3f,sizeof(f));
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++) d[i]=f[s][i];
    for(int i=1;i<=n;i++) f[i][i]=0;
    d[s]=0;
    vis[s]=true;
    for(int i=1;i<=n;i++){
        int minans=0x3f3f3f3f,u;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&d[j]<minans){
                minans=d[j];
                u=j;
            }
        vis[u]=true;
        for(int v=1;v<=n;v++)
            d[v]=min(dis[v],d[u]+f[u][v]);
    }
}

由于代码过长，我们拆分过来讲解：

const int MAXN=1005;
int d[MAXN],vis[MAXN],f[MAXN][MAXN];
int n,m,s;

引入一个辅助数组D，它的每个元素D[i]表示当前所找到的从起点（即源点s ）到其它每个顶点i的距离，vis[i]记录的是i点是否被走过，然后用邻接矩阵存图。

for(int i=1;i<=m;i++){
    int u,v,w;
    cin>>u>>v>>w;
    f[u][v]=min(f[u][v],w);
}

输入顶点数n，边数m，和源点s。初始化。

cin>>n>>m>>s;
memset(f,0x3f,sizeof(f));
memset(d,0x3f,sizeof(d));
memset(vis,false,sizeof(vis));//false代表没有走过
for(int i=1;i<=n;i++) d[i]=f[s][i];//先把最初的值存入d数组
for(int i=1;i<=n;i++) f[i][i]=0;//每个点到自己的距离都是0
d[s]=0;//源点到自己的距离也是0
vis[s]=true;

读取边，存在邻接矩阵中。

下面就是核心代码：

for(int i=1;i<=n;i++){
    int minans=0x3f3f3f3f,u;
    for(int j=1;j<=n;j++)
        if(!vis[j]&&d[j]<minans){
            minans=d[j];
            u=j;//打擂台找到最近的点
         }
     vis[u]=true;//走过打上标记
     for(int v=1;v<=n;v++)
     d[v]=min(d[v],d[u]+f[u][v]);//循环做一遍更新
}

最外层一层循环遍历所有点，内部循环找到距离最近的点，再对所有点做一次更新。

Dijkstra算法的时间复杂度是O(n²),效率要比Floyd算法要高的多，但还是无法处理负权图。

点击此处练练手

Bellman-Ford算法

它的原理是对图进行次松弛操作，得到所有可能的最短路径。其优于Dijkstra算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(nm)。但算法可以进行若干种优化（比如SPFA算法），提高了效率。

代码实现如下：

const int MAXN=100005;
const int MAXM=500005;
int n,m,s,cnt;
int d[MAXN];//记录最短路
bool flag,p;
struct node{
	int u,v,w;//起点，终点，全职
}edge[MAXM];
int main(){
    memset(d,0x3f,sizeof(d));//初始化
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
        cin>>edge[i].u>>edge[i].v>>edge[i].w;//读入边的信息
    d[s]=0;flag=true;
    while(flag){
        cnt++;
        flag=false;
	for(int i=1;i<=m;i++)
	    if(d[edge[i].v]>d[edge[i].u]+edge[i].w){
		d[edge[i].v]=d[edge[i].u]+edge[i].w;//松弛（顺序一定不能反~）
		    flag=true;
		}	 
	if(cnt>=n){//判断是否含有负权回路 
	    p=true;
	    break;
	}
    }
    if(p) cout<<"存在负环"<<endl; 
    else
	for(int i=1;i<=n;i++)
	    if(i!=n) cout<<d[i]<<' '; 
	    else cout<<d[i]<<endl;
    return 0;
}

每次松弛操作实际上是对相邻节点的访问，第 n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过 |V|-1条边，所以可知 Bellman-Ford算法所得为最短路径。

Bellman-Ford算法的好处就是可以判断负环图，这是其他算法所没有的。

点击此处练练手（注意：边界和范围要根据具体题目调整）

SPFA算法

SPFA 算法是 Bellman-Ford算法的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(nm)。

下面是代码的实现：

const int MAXN=100005;
const int MAXM=500005;
int n,m,s,cnt;
int next[MAXM],ver[MAXM],edge[MAXM];
int head[MAXN],d[MAXN];
bool vis[MAXN];
queue <int> q; //SPFA是Bellman-Ford的数组优化版
void add(int u,int v,int w){
    ver[++cnt]=v;edge[cnt]=w;
    next[cnt]=head[u];head[u]=cnt;//链式前向星存图
}
int main(){
    memset(d,0x3f,sizeof(d));
    cin>>n>>m>>s;
    d[s]=0;vis[s]=1;//初始化
    q.push(s);//入队
    for(int i=1;i<=m;i++){
	int u,v,w;
	cin>>u>>v>>w;
	add(u,v,w);//存边
    } 
    while(!q.empty()){
	int u=q.front();//取队首元素
	q.pop();//出队
	vis[u]=0;//出队后去除标记
	for(int i=head[u];i;i=next[i]){//链式前向星的遍历
	    int v=ver[i],w=edge[i];
	    if(d[v]>d[u]+w){//若找到更优的路径，更新
	        d[v]=d[u]+w;
		if(!vis[v]){//没有入过队就入队
		    q.push(v);
		    vis[v]=1;//打上标记 
		}
	    }
	}
    }
    for(int i=1;i<=n;i++)
	if(i<n) cout<<d[i]<<' ';
	else cout<<d[i]<<endl;
    return 0;
}

为了避免最坏情况的出现，在正权图上应使用效率更高的Dijkstra算法。但如果是负权图，只能用SPFA算法和Bellman-Ford算法。

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程一题里非常熟练地使用了一个广为人知的算法（SPFA）求最短路。

然后呢？

100 → 60；

Ag → Cu；

最终，他因此没能与理想的大学达成契约。

所以，接下来要讲的是Dijkstra+堆优化

不难发现，前面Dijkstra的时间复杂度为O(n²)，主要瓶颈在于第一步寻找全局最小值的过程。所以可以对这一部分进行优化，就可以用到优先队列（C++ STL priority_queue）来实现。不会的同学可以参考优先队列详解。

用优先队列可以实现用O(log n)的时间执行一条边的拓展和更新，所以时间复杂度可以优化到O(m log n),远小于O(n²)。话不多说，下面就是代码。

priority_queue<pair<int,int> >q;
//定义大根堆（优先队列）
//pair的第一维是d的相反数（利用相反数把大根堆变成小根堆）
//pair的第二维为节点编号
q.push(make_pair(0,s));
while(!q.empty()){
    int u=q.top().second;
    q.pop();
    if(vis[u]) continue;
    vis[u]=1;
    for(int i=head[u];i;i=next[i]){
	int v=ver[i],w=edge[i];
	if(d[v]>d[u]+w){
	    d[v]=d[u]+w;
	    q.push(make_pair(-d[v],v));
	}
    }
}

由于前面的代码比较详细，所以这里就只有主要部分。

要注意的是，Prim算法的时间复杂度是O(n²)，优化后时间复杂度是O(m log n)，所以说Kruskal算法更适用于稀疏图，Prim算法更适合于稠密图。

点击此处练练手

到这里求最短路的几种常见方法都介绍完了，下面送一个福利。

Dijkstra_priority_queue.cpp

参考资料来源：

百度百科
李煜东《算法竞赛进阶指南》

Hi,DWXmaster!

C++图论（最短路）

图的存储

邻接矩阵

不带权的图

带权图

邻接矩阵的实现

特点

邻接表

链式前向星

特点

最短路

Floyd算法

Dijkstra算法

Bellman-Ford算法

SPFA算法

参考资料来源：

C++图论（最小生成树）

Nginx设置子域名解析

DWXmaster

Comments | 2 条评论

博主 NιghτRαιΩ

博主 /、Ⅱ？

Cancel Reply

无限の域