图的最短路径：Dijkstra算法

Dijkstra算法是一种基于贪心策略的算法。每次新扩展一个路程最短的点，更新与其相邻的点的路程（称为松弛），由于没有存在负边权，所以不会存在一个路程更短的，没有扩展过的点。

因此Dijkstra算法只能处理正边权的图。

示例题目

同Floyd算法中的城市旅游问题

解题代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//最短路径——迪杰斯特拉算法
#include<iostream>
using namespace std;
#define inf 999999;

int city, road;
//城市数量和道路数量

//迪杰斯特拉算法
void dijkstra(int** cityMap,bool* book,int start)
{
	//创建dis数组储存最短路径
	int* dis = new int[city + 1];
	dis[0] = inf;
	for (int i = 1; i <= city; i++) dis[i] = cityMap[start][i];//初始化
	
    //起点标记为true
	book[start] = true;

	int min;//定义最小值变量
	int node=0;//最小值对应的点7
	for (int i = 1; i <= city; i++)
	{
		min = inf;//初始化最小值
		for (int j = 1; j <= city; j++)//循环查找最小值
		{
			if (book[j] == false && dis[j] <= min)
			{
				min = dis[j];
				node = j;
			}
		}

		book[node] = true;//标记找到的点N
        //此时标记到的点N到起点的距离就是起点到点N的最短路径（因为我们每次都找最短的）
        //对点N进行扩展
		for (int k = 1; k <= city; k++)//在点N的基础上，遍历其他点
		{
			if (cityMap[node][k] < 999999)//如果点N到k点有路径
			{
				if (dis[k] > (dis[node] + cityMap[node][k]))//如果起点到k点的路径大于起点到点N再到k点的路径
				{
					dis[k] = dis[node] + cityMap[node][k];//更新一下最短路径，即经过点N再到点k更短
				}
			}
		}
	}

	for (int i = 1; i <= city; i++) cout << dis[i] << " ";
	delete [] dis;//数组的释放
}

int main()
{
	cin >> city >> road;
	//初始化地图
	int** cityMap = new int*[city + 1];
	for (int i = 0; i < city + 1; i++)
	{
		cityMap[i] = new int[city + 1];
		for (int j = 0; j < city + 1; j++)
		{
			cityMap[i][j] = inf;
		}
	}
	for (int i = 1; i <= city; i++) cityMap[i][i] = 0;

	//初始化标记数组
	bool* book = new bool[city + 1];
	for (int i = 1; i <= city; i++) book[i] = false;

	//录入地图数据
	int a, b,c;
	for (int i = 0; i < road; i++)
	{
		cin >> a >> b >> c;
		cityMap[a][b] = c;
	}

	dijkstra(cityMap,book,1);//最短路径

	return 0;
}

算法核心部分

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
//迪杰斯特拉算法
void dijkstra(int** cityMap,bool* book,int start)
{
	//创建dis数组储存最短路径
	int* dis = new int[city + 1];
	dis[0] = inf;
	for (int i = 1; i <= city; i++) dis[i] = cityMap[start][i];//初始化
	
    //起点标记为true
	book[start] = true;

	int min;//定义最小值变量
	int node=0;//最小值对应的点7
	for (int i = 1; i <= city; i++)
	{
		min = inf;//初始化最小值
		for (int j = 1; j <= city; j++)//循环查找最小值
		{
			if (book[j] == false && dis[j] <= min)
			{
				min = dis[j];
				node = j;
			}
		}

		book[node] = true;//标记找到的点N
        //此时标记到的点N到起点的距离就是起点到点N的最短路径（因为我们每次都找最短的）
        //对点N进行扩展
		for (int k = 1; k <= city; k++)//在点N的基础上，遍历其他点
		{
			if (cityMap[node][k] < 999999)//如果点N到k点有路径
			{
				if (dis[k] > (dis[node] + cityMap[node][k]))//如果起点到k点的路径大于起点到点N再到k点的路径
				{
					dis[k] = dis[node] + cityMap[node][k];//更新一下最短路径，即经过点N再到点k更短
				}
			}
		}
	}

	for (int i = 1; i <= city; i++) cout << dis[i] << " ";
	delete [] dis;//数组的释放
}

可以看到该算法的核心思路：

  1. 找到边权值最小的点
  2. 该点的最短路径就此确定
  3. 在确定该点最短路径的基础上，遍历其他点，更新路径长度（称为松弛）
  4. 重复上述步骤，直到每个点都确定完毕