文章目录


前言

本篇文章讲的是图论里的最短路问题,如果你还没有图论的基础知识,可以看看我之前的文章:

DFS(深度优先算法)  BFS(广度优先算法)邻接表和邻接矩阵、树的遍历 (DFS和BFS)

这些都是关于图论的基本知识。


一、最短路是什么?

最短路径: 从某个点A(位置)到另一个点B(位置)的最短距离,实现方法:点A途中可以经过很多个点C,然后通过不断更新点A到途中点 C 的最短距离,最后实现最短距离到达 点B。

A -> C1 -> C2 -> C3 -> B

最短路径的分类:

单源最短路:图中的一个点到其余各点的最短路径

多源最短路:图中每两个点的最短路径

框架图解:(如果看不清的话,放大浏览器再观看)

 图中稠密图用邻接矩阵,稀疏图用邻接表,具体了解:

邻接表和邻接矩阵、树的遍历 (DFS和BFS)

二、朴素Dijkstra算法

Dijkstra算法(迪杰斯拉算法):该算法的特点是从起始点开始,采用贪心算法的策略,采用加点的的方式,每次遍历到起始点距离最近且从未被访问过的顶点的邻接节点t,将该点t加入集合S中,直到扩展到终点位置。

时间复杂度:O(n ^ 2)

思想(操作):

  • 将图上的点分为两个集合:分别是S集合N集合
    1. S:表示访问过的点(用st数组存储)
    2. N:表示未访问过的点
  • N集合中的点到S集合距离最短依次加入到S集合
  • 用刚到S集合中的点t去更新集合N起始点的距离(这一步也就是松弛操作)

图解:

步骤: dist[ ]:每个点到起始点的距离  st[ ]:是否加入到了s集合中

  1. 初始化距离:把每个点都初始化为0x3f3f3f3f(无穷大)
  2. 进行n层循环:遍历dist数组,找到一个不在S集合中并距离S集合最短的点t,每一层循环都将找到的点t将它放入S集合中(st[t] = true)
  3. 用找到的点t去更新N集合起始点的距离(松弛操作)

代码 + 注释:

const int N = 1e5 + 10;//多少个点
int dist[N];    //每个点到起始点的距离
bool st[N];    //S集合
void dijkstra(){
    memset(dist, 0x3f3f3f3f, sizeof dist);//初始化距离
    dist[1] = 0;
	for(int i = 1; i <= n; i ++){    //进行n次循环
		int t = -1;                  //设找到的点初始化为1
		for(int j = 1; j <= n; j ++){
			if(!st[j] && (t == -1 || dist[j] < dist[t])) 
                //如果该点j没在S集合中并且没更新或者有距离S集合更小的点
				t = j; //找到该点
		} 
		st[t] = true;加入集合S中
		//松弛操作,用该点更新到s的距离
		for(int j = 1; j <= n; j ++){
			dist[j] = min(dist[j], dist[t] + g[t][j]);
		}
	}
	if(dist[n] == 0x3f3f3f3f) puts("impossible");//如果为无穷大说明到不了n点
	else printf("%d", dist[n]);
	
} 

三、堆优化版Dijkstra算法

堆优化版Dijkstra算法堆优化版Dijkstra算法是对朴素Dijkstra算法遍历所有点比较找出距离最近的点这一步骤,使用小根堆(优先队列)对这段代码进行优化:

for(int i = 1; i <= n; i ++){    //进行n次循环
		int t = -1;                  //设找到的点初始化为1
		for(int j = 1; j <= n; j ++){
			if(!st[j] && (t == -1 || dist[j] < dist[t])) 
                //如果该点j没在S集合中并且没更新或者有距离S集合更小的点
				t = j; //找到该点
		} 

时间复杂度:O(m * logn)

思想:                                ​​​​​typedef pair<int, int>PII;

用小根堆priority_queue<PII, vector<PII>, greater<PII>>heap;存储距离和点,堆自动排序,可以排序取距离S集合小的点,然后每次取不在集合S中距离最段的点,再进行松弛操作,最后将松弛操作的点插入小根堆中

步骤:

  1. 初始化距离:把每个点都初始化为0x3f3f3f3f(无穷大),并将1号点放在堆中
  2. 取出堆顶的点,用该点t进行拓展,采用邻接表的数据结构,遍历该点t能到的所有节点
  3. 进行松弛操作,然后把松弛的点距离加入堆中。

代码 + 注释:

typedef pair<int, int>PII; //pair<int, int>用来存两个值
const int N = 1e5 + 10;
int dist[N];
bool st[N];

int dijkstra(){
	memeset(dist, 0x3f3f3f3f, sizeof dist);//初始化距离
	dist[1] = 0;
	priority_queue<PII, vector<PII>, greater<int>>heap;//定义小根堆
	heap.push({0, 1}); //一定要距离在第一位,因为小根堆是根据第一个数据来排序
	
	while(heap.size()){
		PII t = heap.top();        //取堆顶距离最小的元素
		heap.pop();
		int distance = t.first, ver = t.second;//取出距离和点
		if(st[ver]) continue;//如果该点以及加入了集合S中,就continue
		st[ver] = true;      //否则加入该点
		
		for(int i = h[ver]; i != -1; i = ne[i]){    //遍历该点能到的点的位置
			int j = e[i];
			if(dist[j] > distance + w[i]){    //进行松弛操作
				dist[j] = distance + w[i];    
				heap.push({dist[j], j});        //入堆
			}
		}
	}
	if(dist[n] == 0x3f3f3f3f) return -1;
	else return dist[n];
}

四、Bellman_Ford算法

Bellman_Ford算法(贝尔曼-福特算法):该算法比Dijkstra算法更具有普遍性,Dijkstra算法采用的是贪心思想,而Bellman_Ford采用的是动态规划,因为它对边没有要求,可以处理负权边与负权回路,也可以求边数限制的最短路,缺点是它的时间复杂度比较高,不能判断负环

时间复杂度:O(n * m)

思想:结构体来存储图对所有的边(重点)进行n - 1轮松弛操作,就是第一轮对所有边进行松弛,得到的是源点最多经过一条边到达其他顶点的最短距离,第二轮对所有的边进行松弛,得到的是最多经过两条边到其他顶点的最短距离,以此类推,最后达到n

图解:

步骤:

  1. 循环n - 1次,每次循环更新每条边的最短距离
  2. 备份一份上次迭代dist距离的数据,防止串联
  3. 用以后的dist[j]进行拓展,松弛操作

代码 + 注释:

const int N = 1e5 + 10;
int dist[N];//距离
int back[N];//备份的数据

struct Edge{
	int a, b, w;
}edge[N];

int bellman_ford(){
	memset(dist, 0x3f3f3f3f, sizeof dist); //初始化距离
	dist[0] = 1;
	for(int  = 0; i <= k; i ++){        //可以求只经过k条边(限制边数)
		memcpy(back, dist, sizeof dist);    //备份防止串联
		for(int j = 1; j <= n; j ++){        //遍历每个点
			int a = edge[i].a, b = edge[i].b, w = edge[i].w;    //取值
			dist[b] = min(dist[b], back[a] + w);    //松弛操作
		}
	}
    if(dist[n] > 0x3f3f3f3f / 2) return -1;    //因为存在负权边,所以0x3f3f3f3f要除2
    return dist[n];
} 

五、spfa算法

SPFA算法(全称Shortest Path Faster Algorithm):是Bellman_frod的队优化形式,通常用来求含负权边的的单源最短路问题,以及判断负权环,如果存在负权环就不能用SPFA算法计算最短路

SPFA算法与Bellman_frod的区别SPFABellman_ford队优化版,但Bellman_Ford可以用来求负环的最短路,是因为其循环次数是有限制的,因此不会发生死循环,而SPFA算法不可以求带有负环的最短路,由于用了队列存储,只要发生了更新就会不断的入队,因此有了负权回路就不能用SPFA否则会死循环,但是SPFA可以利用这点来判断图中是否存在负环,如果某个点(非终点)的经过边数达到了n就说明存在负环

时间复杂度:由于SPFA是Bellman_ford优化而来,所以SPFA的最坏的情况是O(n * m),一般情况下是O(n)

对Bellman_ford的代码优化:

for(int j = 1; j <= n; j ++){        //遍历每个点
	int a = edge[i].a, b = edge[i].b, w = edge[i].w;    //取值
	dist[b] = min(dist[b], back[a] + w);    //松弛操作
}

思路:​​​​​​​采用的是类似BFS无权环的思路,设立一个队列来保存待优化的结点,优化时每次取队头结点t,然后遍历队头能经过的边到达的点vt点对所能经过的边的点v进行松弛操作,如果能进行松弛操作,并且v点不在当前队列中,就将v点入队,这样不断进行松弛操作,直到队列为空为止

步骤:

  1. 初始化dist[ ]数组,建立一个队列,将起始点入队
  2. 取出队头进行扩展,并进行松弛操作

代码 + 注释:

const int N = 1e5 + 10;        //多少个点
int e[N], ne[N], w[N], idx, h[N];
void add(int a, int b, int c){    //邻接表的存储方式
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx ++;
} 

int spfa(){
	memset(dist, 0x3f3f3f3f, sizeof dist);    //初始化距离
	dist[0] = 1;                        
	queue<int>q;        //定义队列
	q.push(1);
	st[1] = true;
	
	while(q.size()){
		int t = q.front();        //取出队头
		q.pop();
		st[t] = false;
		
		for(int i = h[t]; i != -1; i = ne[i]){    //遍历t能到的点
			int j = e[i];
			if(dist[j] > dist[t] + w[i]){        //松弛操作
				dist[j] = dist[t] + w[i];
				if(!st[j]){
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
	return dist[n];
}

SPFA算法判读负环的代码 + 注释:

const int N = 1e5 + 10;
int dist[N];
int cnt[N];记录当前点t到源点最短路的边数,
bool spfa(){
    // 这里不需要初始化dist数组为 正无穷/初始化的原因是, 如果存在负环, 那么dist不管初始化为多少, 都会被更新
    queue<int>q;

    //不仅仅是第一个点了, 因为第一个点可能到不了有负环的点, 因此把所有点都加入队列
    for(int i = 1;i <= n; i ++){
        q.push(i);
        st[i] = true;
    }

    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;//如果能进行松弛操作就在当前点的cnt+ 1
                if(cnt[j] >= n){
                    return true;
                }
                if(!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

六、Floyd算法

Floyd算法(弗洛伊德算法又称插点法):采用动态规划的思想,来解决给多源最短路的问题,可以求图中的任意一点x到任意一点y的距离

时间复杂度:O(n ^ 3)        三重循环

算法思路:从图的带权邻接矩阵开始,进行n次迭代更新,每次更新每两个点之间的最短距离,状态方程:f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

步骤:

  1. 初始化:从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大

  2. 对于每一对顶点 i 和 j, 看看是否存在一个顶点 k 使得从 i 到 k 再到 j 比已知的路径更短。如果是更新它。

代码 + 注释:

void Folyd(){
    for (int i = 1; i <= n; i ++ ){    //初始化
       for(int j = 1; j <= n; j ++){
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
        }
    }
    //动态规划
    for(int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}


总结

以上就是我所了解的几个最短路算法,可能还有很多待优化的地方,希望大家能指正。

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐