时间戳

首页 > 技术文章 > 最短路径问题

最短路径问题

smth 2021-06-06 20:15 原文

Dijkstra算法

Dijkstra算法一般是用来处理单源最短路径问题,求得是任意节点到源点得最短路径！！！

单源最短路径问题：给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径问题。

但要注意的是！！Dijkstra算法适用要求必须每个边的权重都为正数
为什么呢？

如果权值存在负数，那么被派生出来的可能是更短的路径，这就需要过程可以回溯，之前的路径需要被更短的路径替换掉，而Dijkstra算法是不能回溯的。它每一步都是以当前最优选择为前提的。

Dijkstra算法运行速度比Bellman-Ford算法要快，但是其要求图中不能包含负权重的边。

Dijkstra算法的操作+原理

配合视频食用
推荐视频1：【算法】最短路径查找—Dijkstra算法
推荐视频2：Dijkstra(迪杰斯特拉)算法理解
效果更佳

谈一下个人对Dijkstra算法的理解，Dijkstra算法是通过贪心思想实现的
Dijkstra主要由一个集合构成，我们设为S，S是用来存放收集到的节点，S初始为空

1、首先先从源点出发，将源点收入集合S，查找和源点相连的所有节点，将相连节点到源点的距离设为相连节点到源点的最短距离，记录相连节点的经过的上一个节点为源点
2、然后对于所有未收入集合的节点查找到距离最小的节点P，将该节点放入S节点，接着对于P相连的所有并且未曾进入过S集合的节点进行距离的计算，如果发现计算后的距离比原先该点到源点的最短距离要小就进行更新，否则不变。
操作2重复进行直至所有节点都被存入进S过（还是看视频清楚）

视频里面操作2分两步：
1.每次从未标记的节点中选择距离出发点（源点）最近的节点（找到距离源点最短路径的点才能跟新相邻点的最短路径），标记，收录到S集合中
2.计算刚加入节点A的临近节点B的距离（不包含标记节点），若（节点A的距离+节点A到B的距离）<节点B的距离，就更新节点B的距离和前面点

为什么这样可以实现最短路径呢，我的理解是对于任意一个节点，dist[v]存的是该节点到源点的当前最短距离，如果该节点到源点的路径只有一条，那么该路径就是最短路径，但如果有多条边呢，假设源点到当前节点有两条路径，其中一条路径的长度在之前已经被存入到dist[v]，那么在另一条路径，离当前节点的最近节点加上两个节点的距离就是这条路径的距离，与已经存在的dist[v]进行比较，得出源点到该节点的最短路径，多条路径同理。
反正就是在一次又一次的不断更新后每个点存储的距离都是到源点的最短距离
在这里插入图片描述
比如这张图，1先标记，从1开始出去又两个节点，分别为2，3，1到2距离1，1到3距离9，将其与初始化（初始源点到任一点的距离都是无穷大）的1到2距离，1到3距离进行比较，重新定义1到2和3的距离
1-2=1，1-3=12 标记1
接着未标记的点找距离源点最小的，也就是2，2标记，2出去有两个点为3，4，2到4距离为3，1+3<max,所以源点到4距离为4，2到3距离为9,1+9>12,更新源点到3的最短距离
1-2=1
1-3=10
1-4=4 标记1 2
往后同理
在不断找最小路径的同时跟新每个节点到源点的最短距离（每一个点的相邻点都记录了到源点的最短距离，所以该点到源点的最短距离就是相邻点的最短距离+边的最小值emmm我觉得这个解释应该清楚了，想的和表述的总是没法一致），最终得到的就是源点到各点最短距离

最重要的当然是放代码了

参考例题：
在这里插入图片描述

算法实现：

void Dijkstra(int n,int beg)
{
	collected[beg] = 1;//标记收录
	dist[beg] = 0;
	consume[beg] = 0;
	for (int i = 0; i < n; i++)
		if (path[beg][i].len!=MAXN) {
			dist[i] = path[beg][i].len;
			consume[i] = path[beg][i].pri;
			last[i] = beg;
		}
	while (1)
	{
		int rebeg = FindMinDist(n);//找出未标记节点的最小值
		if (rebeg == -1) break;
		collected[rebeg] = 1;
		for (int i = 0; i < n; i++)//更新未标记的最小节点的相邻节点的相关数据
		{
			if (!collected[i] && path[rebeg][i].len!=MAXN)
			{
				if (dist[rebeg] + path[rebeg][i].len < dist[i])
				{
					dist[i] = dist[rebeg] + path[rebeg][i].len;
					consume[i] = consume[rebeg] + path[rebeg][i].pri;
					last[i] = rebeg;
				}
				else if (dist[rebeg] + path[rebeg][i].len == dist[i] && consume[rebeg] + path[rebeg][i].pri < consume[i])
				{
					consume[i] = consume[rebeg] + path[rebeg][i].pri;
					last[i] = rebeg;
				}
			}
		}
	}
}
int FindMinDist(int n)
{
	int Min = MAXN, Minp = -1;
	for (int i = 0; i < n; i++)
	{
		if (!collected[i] && dist[i] < Min)
			Min = dist[i], Minp = i;
	}
	return Minp;//如果minp！=-1存在未收录的节点
}

完整代码

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 10000000
struct node
{
	int len, pri;
};
int dist[800];//这个数组用来存储节点到源点的最短距离
int consume[800] = { 0 };//记录各节点到源点的消费
int last[800];//记录该节点经过路径的上一个节点
int collected[800] = { 0 };//标记数组
struct node path[800][800];//初始化节点之间的距离和车费
void Inti(int n);
void BuildGraph(int m);
void Dijkstra(int n,int beg);
int FindMinDist(int n);
int main()
{
	int N, M, S, D;
	cin >> N >> M >> S >> D;
	Inti(N);
	BuildGraph(M);
	Dijkstra(N,S);
	cout << dist[D] << " " << consume[D];
	return 0;
}
void Dijkstra(int n,int beg)
{
	collected[beg] = 1;//标记收录
	dist[beg] = 0;
	consume[beg] = 0;
	for (int i = 0; i < n; i++)
		if (path[beg][i].len!= MAXN) {
			dist[i] = path[beg][i].len;
			consume[i] = path[beg][i].pri;
			last[i] = beg;
		}
	while (1)
	{
		int rebeg = FindMinDist(n);//找出未标记节点的最小值
		if (rebeg == -1) break;
		collected[rebeg] = 1;
		for (int i = 0; i < n; i++)//更新未标记的最小节点的相邻节点的相关数据
		{
			if (!collected[i] && path[rebeg][i].len!=MAXN)//未收录，有连接
			{
				if (dist[rebeg] + path[rebeg][i].len < dist[i])
				{
					dist[i] = dist[rebeg] + path[rebeg][i].len;
					consume[i] = consume[rebeg] + path[rebeg][i].pri;
					last[i] = rebeg;
				}
				else if (dist[rebeg] + path[rebeg][i].len == dist[i] && consume[rebeg] + path[rebeg][i].pri < consume[i])
				{
					consume[i] = consume[rebeg] + path[rebeg][i].pri;
					last[i] = rebeg;
				}
			}
		}
	}
}
int FindMinDist(int n)
{
	int Min = MAXN, Minp = -1;
	for (int i = 0; i < n; i++)
	{
		if (!collected[i] && dist[i] < Min)
			Min = dist[i], Minp = i;
	}
	return Minp;//如果minp！=-1存在未收录的节点
}
void BuildGraph(int m)
{
	int c1, c2, l, p;
	for (int i = 0; i < m; i++)
	{
		cin >> c1 >> c2 >> l >> p;
		path[c1][c2].len = path[c2][c1].len = l;
		path[c1][c2].pri = path[c2][c1].pri = p;
	}
}
void Inti(int n)
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			path[i][j].len = path[j][i].len = MAXN;
			//我之前是把没有路设为0，但是一个点到他本身的距离也是0，所有最好设成无穷大
			path[i][j].pri = path[j][i].pri = 0;
		}
	for (int i = 0; i < n; i++) {
		dist[i] = MAXN;
		last[i] = -1;
	}
}

Floyd算法

Floyd算法实际上是一个动态规划算法
Floyd算法和Dijkstra算法最大的区别就是，Dijkstra算法dist数组存放的是任意一个节点到源点的最短距离，这是一个一维数组，而Floyd算法算法的dist数组是一个二维数字，dist[i][j]表示i，j两个节点的最短距离。
在查找任意两个节点的最短路径的时候，Floyd算法是在之前已得到的两点之间最短路径的基础上跟新节点之间的最短路径，但其实两个算法的时间复杂度都是O(N^3)（如果找全部节点的最小距离）
dijkstra单找源点到终点实际复杂度是O（n^2)

原理

配合视频Floyd算法图解食用效果最佳
n个节点，任取一个节点，比较任意两个相邻节点之间的之间路径与经过节点的路径哪一个小，将小的距离定义为i，j节点的最短距离，往后同理
主要算法实现

void Floyd(int n)
{
	for (int k = 0; k < n; k++)//k指的是第几个节点用来判断是否存在中间节点到两个节点的距离和小于两节点直接距离
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
			{
				if (dist[i][k].len + dist[k][j].len < dist[i][j].len)
				{
					dist[i][j].len = dist[i][k].len + dist[k][j].len;
					dist[i][j].pri = dist[i][k].pri + dist[k][j].pri;
				}
				else if (dist[i][k].len + dist[k][j].len == dist[i][j].len && dist[i][k].pri + dist[k][j].pri < dist[i][j].pri)
					dist[i][j].pri = dist[i][k].pri + dist[k][j].pri;
			
			}
}

还是那道题：

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1000000
typedef struct
{
	int len, pri;
}Node;
Node dist[800][800];//记录任意两点之间的路径（路径相同车费最少）
void Inti(int n);
void BuildGraph(int m);
void Floyd(int n);
int main()
{
	int N, M, S, D;
	cin >> N >> M >> S >> D;
	Inti(N);
	BuildGraph(M);
	Floyd(N);
	cout << dist[S][D].len << " " << dist[S][D].pri;
	return 0;
}
void Floyd(int n)
{
	for (int k = 0; k < n; k++)//k指的是第几个节点用来判断是否存在中间节点到两个节点的距离和小于两节点直接距离
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
			{
				if (dist[i][k].len + dist[k][j].len < dist[i][j].len)
				{
					dist[i][j].len = dist[i][k].len + dist[k][j].len;
					dist[i][j].pri = dist[i][k].pri + dist[k][j].pri;
				}
				else if (dist[i][k].len + dist[k][j].len == dist[i][j].len && dist[i][k].pri + dist[k][j].pri < dist[i][j].pri)
					dist[i][j].pri = dist[i][k].pri + dist[k][j].pri;
			
			}
}
void BuildGraph(int m)
{
	int c1, c2, l, p;
	for (int i = 0; i < m; i++)
	{
		cin >> c1 >> c2 >> l >> p;
		dist[c1][c2].len = dist[c2][c1].len=l;
		dist[c1][c2].pri = dist[c2][c1].pri=p;
	}
}
void Inti(int n)
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dist[i][j].len=dist[i][j].pri=MAXN;
}

总结：

Floyd算法是把所有点列举并判断能不能是两个家电距离更短
Dijkstra算法是每次拓展一条最短的路直到找到

推荐阅读