Dijkstra（迪杰斯特拉）算法

晚上是个好时间去刷题，我今天就看了Dijkstra算法，名字倒挺不好读的，所以我进行了深入思考，终于把一个看起来很难的算法，实际上不太简单的算法弄懂了，先来介绍一下Dijkstra

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

——来自《百度百科》

这个荷兰科学家还是比较厉害的。

我们就开始看Dijkstra了。

Dijkstra是一个基于贪心的最短路算法，不能处理权值为负的情况，是单源的最短路算法的一种

这个算法的主要过程如下：

1.建一个数组d[n]，表示从第n个节点到第1个节点的最短距离，然后初始化d[1]=1，其他的为正无穷。

2.遍历找到一个没有被覆盖的d[x]的最小的节点x，然后标记x

3.尝试x的每个出边(x,y,z)，如果d[y]>d[x]+z,就赋值d[y]=d[x]+z;（z为x到y的距离）；

4.最后重复以上过程，直到所有的点都被标记，就完事儿了

我们就完成了单源最短路径，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[3010][3010],d[3010],n,m;
bool v[3010];
int min(int a,int b)//最小值函数
{
	return a<b? a:b;
}
void dijkstra()//单源最短路径
{
	memset(d,0x3f,sizeof(d));//初始化数组d的元素为正无穷
	memset(v,0,sizeof(v));//初始化数组v为0
	d[1]=0;//第一个节点到它自己的距离为0
	for(int i=1;i<n;i++)//开始循环
	{
		int x=0;
		for(int j=1;j<=n;j++)//内层循环
		{
			if(!v[j]&&(x==0||d[j]<d[x]))
			x=j;
		}
		v[x]=1;
		for(int y=1;y<=n;y++)//类似一个动态规划的过程但不是
		d[y]=min(d[y],d[x]+a[x][y]); 
	}
}
int main()
{
	cin>>n>>m;//输入一个n*m的邻接矩阵
	memset(a,0x3f,sizeof(a));//初始化数组a为正无穷
	for(int i=1;i<=n;i++)
	a[i][i]=0;//一个点到它自己的距离为0
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;//x到y的距离是z
		a[x][y]=min(a[x][y],z);//x到y的距离要保证是小的
	}
	dijkstra();//开始Dijkstra
	for(int i=1;i<=n;i++)//输出结果
	cout<<d[i]<<endl;
	return 0;//完美撒花！
}

时间复杂度

O(n2)O(n^2)

下期预告：

高级素数筛或者单源最短路径优化版