Dijkstra算法

编程与算法

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

说的好厉害的样子，其实就是求有向图中单源最短路径的问题。

其实理解floyd或者贪心最小生成树后，应该很容易理解这个算法的。

核心思路

核心思想是引入两个向量(数组)去记录源到各点的最短距离，和该点是否被访问过。

算法简介

首先定义一个数组dis[N]表示源点到各点的距离。
再定义一个数组visit[N]表示该点是否被访问。

首先将源点st标记为访问visit[st] := true,然后将权值矩阵的一行map[st]赋值给dis.

  • 寻找dis中最小且未被访问过的点k,即dis[k] == min{dis} && visit[k] == false.
  • 以k点为中间点，根据松弛方程dis[i]:= min{ map[st,k] + map[k,i], map[st,i] }更新向量dis.
  • 将k点标记为访问visit[k] := true

重复上述过程直到所有的点被标记完，或者有的点不可到达跳出循环。

算法实现

还是写C++吧：

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
const int N = 105;
const int INF = 0x1f1f1f1f;

int map[N][N];
int dis[N];
bool visit[N];

void dijkstra(int st,int n){
	memset(dis,INF,sizeof(dis));
	memset(visit,0,sizeof(visit));
	for(int i=1;i<=n;i++){
		dis[i] = map[st][i];
	}
	dis[st] = 0;
	visit[st] = 1;
	int minx = INF;
	int index = st;
	for(int i=1;i<=n;i++){
		minx = INF;
		for(int j=1;j<=n;j++){
			if(!visit[j] && dis[j] < minx){
				minx = dis[j];
				index = j;
			}
		}
		if(minx == INF)
			break;
		visit[index] = 1;
		for(int j=1;j<=n;j++){
			if(dis[j] > map[index][j] + minx){
				dis[j] = map[index][j] + minx;
			}
		}
	}
}