---

最短路径专题1 Dijkstra 最短距离（朴素版）

原创 已于 2023-10-03 13:03:23 修改 · 粉丝可见 · 114 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132165326

题目：

样例：

cobol<br/>6 6 0 2<br/>0 1 2<br/>0 2 5<br/>0 3 1<br/>2 3 2<br/>1 2 1<br/>4 5 1<br/>

3

思路：

像这种数据范围小的，我们可以用邻接矩阵的方式，做 Dijkstra，

Dijkstra 的算法思想就是，就是 拿一个 探头 t 遍历一遍所有结点，看一下那个距离最短，然后标记我们下一步该走哪一个结点，然后在遍历一遍更新我们走动后所有结点最短距离即可

代码详解如下：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510,INF = 0x3f3f3f3f3f;

int n,m,start,last;

int d[N][N];	// 记录各个结点间的距离
int dist[N];	// 记录最短距离
bool st[N];		// 标记走动的结点

int Dijkstra()
{
	memset(dist,INF,sizeof dist);
	dist[start] = 0;	// 刚开始我们还没开始走动，最短距离为 0
	// 开始探头走动
	for(int i = 0;i < n;++i)
	{
		int t = -1;	// t 作为探头
		for(int j = 0;j < n;++j)
		{
			// 如果 t 还探得，或者 结点t 比 结点 j 的距离还要大 并且 结点 j 还未走动 
			// 我们更新探头
			if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
		}

		st[t] = true;	// 标记我们走动的结点

		// 遍历所有结点，t 到结点 j 的最短距离 加上我们 当前 t 的最短距离
		for(int j = 0;j < n;++j)
		{
			// 如果我们下一个走动的结点 j 比 t 走动的结点还要大，那我们就走动 t 这个结点
			if(dist[j] > dist[t] + d[t][j])
			{
				dist[j] = dist[t] + d[t][j];	// 更新最短距离结点
			}
		}
	}
	return dist[last];	// 返回终点最短距离
}

int main()
{
	memset(d,INF,sizeof d);	// 初始化各个结点距离
	cin >> n >> m >> start >> last;
	while(m--)
	{
		int a,b,c;
		cin >> a >> b >> c;
		// 记录如果两个节点之间出现两个路径，我们记录走动最短的一个路径即可
		d[a][b] = d[b][a] = min(d[a][b],c);
	}

	int ans = Dijkstra();
	// 如果我们终点最短距离接近无穷大，说明无法到达
	// 这里 INF / 2 是因为有可能出现 负环情况，所以我们要的是 INF / 2
	if(ans >= INF / 2) puts("-1");
	else cout << ans << endl;
	// 否则直接输出最短距离
	return 0;
}

最后提交：