算法之迪杰斯特拉（dijkstra）形象化

用处：求到某点的最短路径

图形解释：（这里引用一篇大佬写的博客，他写的图形解释非常清晰）

算法之迪杰斯特拉（dijkstra）非常详细介绍_PRML_MAN的博客-CSDN博客_迪杰斯特拉

---

补充理解：

为了帮助大家理解我这里采用一个

比喻的例子来帮助大家来理解该算法

背景引入：

病毒为了攻占所有的细胞

偷偷联系一个连通的细胞群

中的一个间谍细胞体内

作为初母体

然后进行它的感染计划

聪明的它决定感染前找到

从初母体出发找到

感染每个细胞的最短路径

我们可以把要找的某点称为初母体

（ 这里的家就是我们所说的母体）

这个病毒初母体能够感染

与它连通一次的所有细胞

并且在这些所有被感染的细胞中

找到 和初母体最短距离的细胞（v2细胞）

作为新的母体用来提供感染周围细胞的养分

提供完后找到距初母体最近的感染细胞

并因为该细胞被榨干

废除该细胞为普通感染细胞

 

然后感染未作为母体

且距离初母体最近的细胞

作为母体重复下去

总结下来步骤如下

1.找到初母体所在位置

2.母体感染与它连通的所有细胞

3.废除该母体作为普通细胞

4.找到距初母体最近的感染细胞（被废除的细胞不能算）

5.将其作为母体（回到步骤2，直到所有的细胞都被感染结束）

---

例题引入：

为了大家更加理解迪杰斯特拉算法

这里引入一个题目帮助大家理解

思路：

用两次 迪杰斯特拉

分别找到去和返回的路径的和

然后比较所有的点来找到所需要走的

最长路径即可

注意:

for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
//对所有方向进行反向，找到反向后感染最快的路径即到达x点的最短路径所在
			swap(tr[i][j], tr[j][i]);
		}
	}

这里找返回路径的时候通过

反转tr就可以实现

因为反转了所有的方向

---

代码详解：

#include
using namespace std;
const int N = 1006;
int d[N],dvis[N],tr[N][N],back[N];
int n, m, x;
void distla() {
	memset(dvis, 0, sizeof(dvis));
	memset(d, 127, sizeof(d));//赋最大值，表示距离无限远
	d[x] = 0;//*让初母体所在位置为0，即从初母体位置开始感染
 
	for (int i = 1; i <= n; i++) {
 
		int index = -1;
		for (int j = 1; j <= n; j++)//找出被感染过的最短的路径，并使该点成为新的母体
			if (!dvis[j] &&(index == -1 || d[j] < d[index]))
				index = j;
 
		dvis[index] = 1;//标记该母体死亡
 
		for (int j = 1; j <= n; j++) {
			d[j] = min(d[j],d[index]+tr[index][j]);
			//感染母体周围连通且未被感染的点
		}
	}
}
 
int main() {
	cin >> n >> m >> x;
	int t1, t2, t3;
	memset(tr, 127, sizeof(tr));
	for (int i = 1; i <= m; i++) {
		cin >> t1 >> t2 >> t3;
		tr[t1][t2] = min(tr[t1][t2],t3);//取t1到t2的最短时间
		//标记t1到t2的方向，以及所花费的时间
	}
 
	distla();
	memcpy(back, d, sizeof(back));//将d数组copy到d数组中
 
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {//对所有方向进行反向，找到反向后感染最快的路径即到达x点的最短路径所在
			swap(tr[i][j], tr[j][i]);
		}
	}
	distla();
	int maxx = 0;
	for (int i = 1; i <= n; i++) {//找到返回和到达的最短路径
		maxx = max(d[i] + back[i], maxx);
	}
	cout << maxx;
	return 0;
}

PS:加油加油加油加油加油