【复习】 最短路径问题

发布于 2019-07-11  32 次阅读


前置知识

图(树)的存储——邻接表

邻接表是树与图结构的一般化存储方式,可以看成“带有索引数组的多个数据链表”构成的结构集合。

什么意思?

如图所示,这是一个存储了6个数据节点 v1~v6 的邻接表结构。这6个数据被分成4类,通过表头数组 head 可以定位到每一类所构成的链表进行遍历访问。

img

当需要插入新的数据节点时,我们可以通过表头数组 head 定位到新的数据节点所属类别的链表表头,将新数据在表头位置插入。如下图所示,在邻接表中插入了属于第五类的新数据节点 v7 。

img

具体的来说。。。

在一个具有 n 个点 m 条遍的有向图结构中,我们可以把每条边所属的“类别”定义为该边的起点编号。这样所有边被分成 n 类,其中第 x 类就由“从 x 出发的所有边”构成。通过表头 head[x] ,我们很容易定位到第 x 类所对应的链表 ,从而访问从点 x 出发的所有边。

img

如图是在领接表中插入一张5个点、6条边的有向图之后的状态。这6条边按照插入的顺序依次是(1,2),(2,3),(2,5),(3,5),(5,4),(5,1)。左侧展示了这个邻接表存储的宏观信息,右侧展示了采用“数组模拟链表”的实现方式时,内部数据的实际存储方式。 head 与 next 数组中保存的是“ ver 数组的下标”,相当于指针,其中0表示指向空。ver 数组存储的是每条边的终点,是真实的图数据。

代码如下:

//加入有向边(x,y),权值为z
void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;//真实数据
    next[tot]=head[x],head[x]=tot;//在表头x处插入
}

//访问从x出发的所有边
for (int i=head[x];i;i=next[i])
{
    int y=ver[i],z=edge[i];
    //找到了一条有向边(x,y),权值为z
}

这样就实现了用数组模拟链表的方式存储一张带权有向图的邻接表结构

单源最短路径

说完邻接表存储,开始正题

图的存储有好多种,我主要在用的一般就是邻接矩阵和邻接表(捂脸)

邻接矩阵在使用的时候有一个坏处,那就是空间复杂度过大,而邻接表空间复杂度则相对较小

先看例题:

题目地址

这是一道弱化版的单源最短路径问题,其与加强版的区别就是图有没有被特殊构造过。

这道题有两种做法。

第一种做法就是广为人知的dijkstra算法,中文翻译迪杰斯特拉算法

Dijkstra算法的流程如下:

1.初始化dist[1]=0,其余节点的dist值为正无穷大。

2.找出一个未被标记的、dist[x]最小的节点x,然后标记节点x。

3.扫描节点x的所有出边 (x,y,z) ,若 dist[y]>dist[x]+z,则使用dist[x]+z 更新 dist[y]。

4.重复上述2~3两个步骤,直到所有节点都被标记。

来几个图加深理解:

(令start=1)
第一轮循环找到dis值最小的点1,将1变成白点,对所有与1相连的蓝点的dis值进行修改,使得dis[2]=2,dis[3]=4,dis[4]=7
第二轮循环找到dis值最小的点2,将2变成白点,对所有与2相连的蓝点的dis值进行修改,使得dis[3]=3,dis[5]=4
第三轮循环找到dis值最小的点3,将3变成白点,对所有与2相连的蓝点的dis值进行修改,使得dis[4]=4
感谢 little_sun 的图

比较神奇的一点是,Dijkstra不能用在有负权边的图上

那么为什么呢?

我们来看看下面这张图:

Dijkstra 算法基于贪心思想,我们通过不断选择全局最小值进行标记和拓展,最终可以得到起点1到每个节点的最短路径的长度。

朴素的Dijkstra 算法的时间复杂度为O(n^2),显然达不到此题的要求,时间复杂度的主要瓶颈在于第一步的寻找全局最小值的过程。这时候,我们就只需要利用小根堆对dist数组进行维护就好了,时间复杂度可以优化到O(m log n)。

Dijkstra 算法代码如下:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

const int maxn =2510000,maxm=6210000;
const int INF=2147483647;
struct Edge{
    int v,w,next;
}e[maxm*2];
int en,front[maxn];
int n,m,s,t;
inline void AddEdge(int u,int v,int w)
{
    en++;
    e[en].v=v;
    e[en].w=w;
    e[en].next=front[u];
    front[u]=en;
}
struct HeapNode{
    int u,d;
    bool operator< (const HeapNode& rhs) const{
        return d>rhs.d;
    }
};
void Dijkstra()
{
    int d[maxn];
    priority_queue<HeapNode> q;
    for (int i=1;i<=n;i++) d[i]=INF;
    d[s]=0;
    q.push((HeapNode) {s,d[s]});
    while (!q.empty())
    {
        HeapNode x=q.top();
        q.pop();
        int u=x.u;
        if (x.d!=d[u]) continue;
        for (int i=front[u];i>=0;i=e[i].next)
        {
            int v=e[i].v,w=e[i].w;
            if (d[u]+w<d[v])
            {
                d[v]=d[u]+w;
                q.push((HeapNode) {v,d[v]});
            }
        }
    }
    //cout<<d[t]<<endl;
    for (int i=1;i<=n;i++)
        cout<<d[i]<<' ';
    cout<<endl;
}
int main()
{
    memset(front,-1,sizeof(front));
    cin>>n>>m>>s;
    int u,v,w;
    for (int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        AddEdge(u,v,w);
        //AddEdge(v,u,w);
    }
    Dijkstra();
    return 0;
}

此题另外的一种做法就是SPFA(Shortest Path Faster Algorithm)

这个算法最近几年很有名,因为他死了。

img

具体原因可以直接看加强版的最短路问题题目地址

但是即使他死了我们还是要学他(无奈),因为他能判负环,能走负边

这种算法的前身是Bellman-Ford算法,换句话说,他是对Bellman-Ford算法的队列优化算法的别称。

Bellman-Ford算法

给定一张有向图,若对于图中的某一边(x,y,z),有 dist[y]<=dist[x]+z 成立,则称该边满足三角形不等式。若所有边都满足三角形不等式,则 dist 数组就是所求的最短路。

基于迭代思想的 Bellman-Ford算法的流程如下:

1.扫描所有边(x,y,z),若dist[y]>dist[x]+z,则用dist[x]+z更新dist[y]。

2.重复上述步骤,直到没有更新操作发生。

时间复杂度为O(nm)。

SPFA算法

SPFA算法在国际上通称为“队列优化的 Bellman-Ford 算法”,仅在中国大陆流行“SPFA算法”的称谓。

算法流程如下:

1.建立一个队列,最初队列中只含有起点。

2.取出队头节点x,扫描它的所有出边(x,y,z),若 dist[y]>dist[x]+z,则使用dist[x]+z更新dist[y]。同时,若y不在队列中,则把y入队。

3.重复上述步骤,直到队列为空。

在任意时刻,该算法的队列都保存了待拓展的节点。每次入队相当于完成一次dist数组的更新操作,使其满足三角形不等式。一个节点可能会入队、出队多次。最终,图中节点收敛到全部满足三角形不等式的状态。这个队列避免了 Bellman-Ford 算法中对不需要拓展的节点的冗余扫描,在随机图上运行效率为 O(km)级别,其中k是一个较小的常数。

但是在特殊构造的图上,他就会被卡掉,退化为O(nm)级别。

代码如下:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define N 100010

using namespace std;

struct node
{
	int next,to,val;
};
node edge[5*N];

int head[N],tot=0,n,m,t;

void addedge(int x,int y,int z)
{
	tot++;
	edge[tot].val=z;
	edge[tot].to=y;
	edge[tot].next=head[x];
	head[x]=tot;
}

queue<int> q;

int dist[N],v[N];

void spfa()
{
	for (int i=1;i<=n;i++)
		dist[i]=2147483647;
	memset(v,0,sizeof(v));
	dist[t]=0;
	v[t]=1;
	q.push(t);
	while (!q.empty())
	{
		int x=q.front();
		q.pop();
		v[x]=0;
		for (int i=head[x];i;i=edge[i].next)
		{
			int y=edge[i].to,z=edge[i].val;
			if (dist[y]>dist[x]+z)
			{
				dist[y]=dist[x]+z;
				if (!v[y]) q.push(y),v[y]=1;
			}
		}
	}
	for (int i=1;i<=n;i++)
		cout<<dist[i]<<' ';
	cout<<endl;
	return;
}

int main()
{
	int x,y,z;
	cin>>n>>m>>t;
	for (int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		addedge(x,y,z);
	}
	spfa();
	return 0;
}


Cause this is the life. Living is do or die.