迪杰斯特拉算法（Dijkstra）

孟宝亮2022-09-20数据结构1089

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，它用于解决的是有向图中最短路径问题。Dijkstra 算法能够计算出给定起【起始顶点】到【其他所有顶点】的最短路径。

1. 算法过程

我们通过一个例子来分析下 Dijkstra 算法是如何找到最短路径的，首先我们初始化 3 个数组：

  1. 用于记录两顶点之间距离的一维数组 source_others（如果两个顶点没有边则用 M 表示之间的距离，M 是一个较大的数字，我们这里用 65535 表示）；
  2. 用于记录两顶点是否已经找到最短路径的一维 bool 数组 shortest_done（初始化时，自身到自身设置为 true，表示已经找到最短路径，其余都设置为 false）；
  3. 一个用于记录最短路径的一维数组 shortest_path（该矩阵用于记录任意两个顶点经过 k 顶点距离最短，如果 k 不存在，则记录为起始顶点，表示不需要经过任何顶点距离已经是最短，例如：1顶点和6顶点之间，发现经过3顶点距离更短，则该矩阵 [1][6] 位置记录为 3。1顶点和2顶点之间，发现直接距离更短，则[1][2]位置记录为起始顶点1）。

假设：我们的起始顶点为 1 顶点，Dijkstra 算法要计算 1 顶点其他所有顶点的最短路径，则：

初始化：

  1. source_others = [0, 7, 9, M, M, 14]
  2. shortest_done = [true, false, false, false, false, false]
  3. shortest_path = [1， 1， 1， 1， 1， 1]

1.1 第 1 次迭代

  1. 搜索距离 1 顶点最近的顶点是谁？并且记录与其距离。
    • 1->1 已标记最短路径，跳过；
    • 1->2 距离为 7；
    • 1->3 距离为 9；
    • 1->4 距离为 M;
    • 1->5 距离为 M;
    • 1->6 距离为 14；
    • 可知，1->2 的距离为 7， 距离最短。并将 shortest_done[1][2] 标记为 true, 表示 1 顶点到 2 顶点的最短路径找到。
  2. 接下来计算 1 顶点经过 2 顶点到其他顶点的距离是否比 1 直接到其他顶点更短。
    • 1->1 和 1->2->1，由于 1->1 的 shortest_done 标记为 true, 跳过；
    • 1->2 和 1->2->2，由于 1->2 的 shortest_done 标记为 true, 跳过；
    • 1->3 和 1->2->3，1->3 的距离为 9，1->2->3 = 7+10=17, 距离更远，跳过；
    • 1->4 和 1->2->4，1->4 的距离为 M, 1->2->4 = 7+15=22，距离更近，则在 source_others 中将 1->4 的距离从 M 更新成 22, 并在 shortest_path 中记录 1->4 需要经过 2 距离最短，即：shortest_path[1][4] = 2；
    • 1->5 和 1->2->5，1->5 的距离为 M，1->2->5 = 7+M > M，跳过。
    • 1->6 和 1->2->6，1->6 的距离为 14，1->2->6 = 7+M > 14，跳过。

得到：
shortest_done = [true, true, false, false, false, false]
source_others = [0, 7, 9, 22, M, 14]
shortest_path = [1， 1， 1， 2， 1， 1]

1.2 第 2 次迭代

  1. 接下来，从剩余顶点中搜索没有找到最短路径的顶点，并从这些顶点中找出距离最短的顶点：
    • 1->2 已标记，跳过；
    • 1->3 未标记，距离为 9；
    • 1->6 未标记，距离为 14；
    • 可知，1->3 距离最短，并将 shortest_done[1][3] 标记为 true, 表示 1 顶点到 3 顶点的最短路径找到。
  2. 接下来计算起始 1 顶点经过 3 顶点到达其他所有顶点的距离是否比 1 直接到达其他顶点的距离更短。
    • 1->1 和 1->3->1，shortest_done[1][1] 已标记找到最短路径，跳过；
    • 1->2 和 1->3->2，shortest_done[1][2] 已标记找到最短路径，跳过；
    • 1->3 和 1->3->3，shortest_done[1][3] 已标记找到最短路径，跳过；
    • 1->4 和 1->3->4，1->4 的距离为 22，1->3->4 = 9+11=20 < 22，距离更近，则在 source_others 中将 1->4 的距离修改为 20，并在 shortest_path 中记录 1->4 需要经过 3 距离最短，即： shortest_path[1][4] = 3，注意：该值原来是 2，现在更新成 3；
    • 1->5 和 1->3->5，1->5 的距离 M，1->3->5 = 9+M > M，跳过；
    • 1->6 和 1->3->6，1->6 的距离 14，1->3->6 = 9+2 = 11 < 14, 距离更近，则在 source_others[1][6] 记录矩阵为 11，并在 shortest_path[1][6] = 3.

得到：
shortest_done = [true, true, true, false, false, false]
source_others = [0, 7, 9, 20, M, 11]
shortest_path = [1， 1， 1， 3， 1， 3]

1.3 第 3 次迭代

  1. 接着从剩下未在 shortest_done 中标记的顶点中找到距离起始顶点最近的顶点：
    • 1->1, 已标记，跳过；
    • 1->2, 已标记，跳过；
    • 1->3, 已标记，跳过；
    • 1->4，距离为 20
    • 1->5，距离为 M
    • 1->6，距离为 11
    • 可知，1->6 距离最短，将其标记为已找到最短路径，并在 shortest_done[1][6] 标记为 true。
  2. 接下来计算起始 1 顶点经过 6 顶点到达其他顶点的距离是否比直接到达更短：
    • 1->1 和 1->6->1, 已标记，跳过；
    • 1->2 和 1->6->2, 已标记，跳过；
    • 1->3 和 1->6->3, 已标记，跳过；
    • 1->4 和 1->6->4，1->4=20，1->6->4=14+M, 距离更大，跳过；
    • 1->5 和 1->6->5，1->5=M，1->6->5=11+9=20, 距离更近，则在 source_others[1][5] 中记录距离为 23，并记录 shortest_path[1][5]=6；
    • 1->6 和 1->6->6, 已标记，跳过；

得到：
shortest_done = [true, true, true, false, false, true]
source_others = [0, 7, 9, 20, 20, 11]
shortest_path = [1， 1， 1， 3， 6， 3]

1.4 第 4 次迭代

  1. 重复前面的过程，从剩余顶点找到距离起始顶点最近的顶点：
    • 1->1, 已标记找到最短路径，跳过；
    • 1->2, 已标记找到最短路径，跳过；
    • 1->3, 已标记找到最短路径，跳过；
    • 1->4，距离为 20；
    • 1->5，距离为 20；
    • 1->6, 已标记找到最短路径，跳过；
    • 可知，1->4 距离最短，并将 shortest_done[1][4] 标记为 true.
  2. 接下来，计算起始顶点经过 4 顶点到其他顶点的距离是否更近：
    • 1->1 和 1->4->1, 已标记，跳过；
    • 1->2 和 1->4->2, 已标记，跳过；
    • 1->3 和 1->4->3, 已标记，跳过；
    • 1->4 和 1->4->4, 已标记，跳过；
    • 1->5 和 1->4->5，1->5=20，1->4->5=20+6, 距离更远，跳过；
    • 1->6 和 1->6->6, 已标记，跳过；

得到：
shortest_done = [true, true, true, true, false, true]
source_others = [0, 7, 9, 20, 20, 11]
shortest_path = [1， 1， 1， 3， 6， 3]

1.5 第 5 次迭代

  1. 继续重复前面的过程，从剩余顶点中找到距离顶点最近的顶点：
    • 1->1, 已标记找到最短路径，跳过；
    • 1->2, 已标记找到最短路径，跳过；
    • 1->3, 已标记找到最短路径，跳过；
    • 1->4, 已标记找到最短路径，跳过；
    • 1->5，距离为 23；
    • 1->6, 已标记找到最短路径，跳过；
    • 可知，1->5 距离最短，并将 shortest_done[1][5] 标记为 true.
  2. 此时，所有的顶点都已标记找到最短路径。

得到：
shortest_done = [true, true, true, true, true, true]
source_others = [0, 7, 9, 20, 20, 11]
shortest_path = [1， 1， 1， 3， 6， 3]

2. 算法代码

#include <iostream>
#include <list>
using namespace std;

#define M 65535


// 定义顶点
int vertex_size = 6;
int vertex[] = { 1, 2, 3, 4, 5, 6 };

// 定义边
int edges[][6] = {
	{ 0,  7,  9,  M,  M, 14},
	{ 7,  0,  10, 15, M, M},
	{ 9,  10, 0,  11, M, 2},
	{ M,  15, 11, 0,  6, M},
	{ M,  M,  M,  6,  0, 9},
	{14,  M,  2,  M,  9, 0}
};


list<list<int>> dijkstra(int source_vertex)
{
	// 用于记录起始点到其他各点的距离
	int *source_others = new int[vertex_size];
	// 用于记录起始点到其他点最短路径
	int *shortest_path = new int[vertex_size];
	// 用于记录是否已经找到最短路径
	bool *shortest_done = new bool[vertex_size];

	// 初始化辅助数组
	for (int i = 0; i < vertex_size; ++i)
	{
		source_others[i] = edges[source_vertex][i];
		shortest_path[i] = source_vertex;
		shortest_done[i] = false;
	}

	// 将起始节点到起始节点路径标记已经找到，即：忽略计算
	shortest_done[source_vertex] = true;

	// 开始计算起始顶点到其他顶点的最短路径
	for (int i = 0; i < vertex_size; ++i)
	{

		// 假设到起始到起始为最短距离的顶点
		int nearest_vertex = source_vertex;
		// 假设 M 为最大距离
		int nearest_weight = M;

		// 经过 for 循环会找到距离最近的顶点，并获得其距离
		for (int j = 0; j < vertex_size; ++j)
		{
			if (!shortest_done[j] && (source_others[j] < nearest_weight))
			{
				nearest_vertex = j;
				nearest_weight = source_others[j];
			}
		}

		shortest_done[nearest_vertex] = true;

		// 更新经过该顶点到其他顶点的最短距离
		for (int k = 0; k < vertex_size; ++k)
		{
			if (!shortest_done[k] && (nearest_weight + edges[nearest_vertex][k] < source_others[k]))
			{
				// 起始点到 k 顶点的最短距离
				source_others[k] = nearest_weight + edges[nearest_vertex][k];
				// 记录起始点到 k 顶点经过那个顶点
				shortest_path[k] = nearest_vertex;
			}
		}
	}

	// 输出起始点到各个顶点的最短路径
	list<list<int>> results;
	for (int i = 0; i < vertex_size; ++i)
	{
		list<int> path;

		// 回溯路径
		int back_vertex = i;
		path.push_front(back_vertex + 1);
		while (true)
		{
			back_vertex = shortest_path[back_vertex];
			path.push_front(back_vertex + 1);
			if (back_vertex == source_vertex) break;
		}
		
		results.push_back(path);
	}

	delete[] source_others;
	delete[] shortest_path;
	delete[] shortest_done;

	return results;
}

int main()
{
	auto paths = dijkstra(0);  // 起始为 1 顶点
	for (auto &path : paths)
	{
		for (auto v : path)
		{
			cout << v << " ";
		}
		cout << endl;
	}


	return 0;
}

程序输出结果：

1 1
1 2
1 3
1 3 4
1 3 6 5
1 3 6

我们打印下这三个辅助数组的值：

source_others:
0   7   9  20  20  11

shortest_path:
0   0   0   2   5   2

shortest_done:
true   true   true   true   true   true

这个结果和我们前面手算的结果是一致的。

未经允许不得转载：一亩三分地 » 迪杰斯特拉算法（Dijkstra）
1 赞

文章目录

©2024 一亩三分地 京ICP备2021009384号-1anbei 冀公网安备13050302001966号