51工具盒子

依楼听风雨
笑看云卷云舒,淡观潮起潮落
当前位置：工具盒子 > 白嫖帮 > 正文

迪杰斯特拉算法（Dijkstra）

2024-11-19 分类：白嫖帮 阅读(1) 评论(0)

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

  1. 算法过程 {#title-0} ==================

我们通过一个例子来分析下 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 次迭代 {#title-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 次迭代 {#title-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 次迭代 {#title-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 次迭代 {#title-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 次迭代 {#title-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]

  1. 算法代码 {#title-6} ==================
#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

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

赞(1)
未经允许不得转载：工具盒子 » 迪杰斯特拉算法（Dijkstra）
标签：

厉飞雨

众生皆苦，唯有自渡！

相关推荐

最新文章

猜你喜欢

快捷分类

云服务器 日常运维 在线免费 开源工具 科学上网 开发笔记 区块链 白嫖帮 新视野 人工智能 网赚思路 Python笔记 Php笔记 Java笔记 链知识 币知识 IOS笔记 Android笔记 Mysql C语言笔记 前端开发 R笔记 Go笔记 mybatis笔记 Golang笔记 数据库 市场营销 软件教程 vps Rust笔记 软件使用 经验分享 Stable Diffusion chatgpt Midjourney 操作系统 Photoscape 加密货币 挖矿 Coze Meta 网络安全 网络运营 开源软件 Github ComfyUI 数字人 Docker笔记 Claude Oracle web3 linux windows mac redis git笔记 nginx kafka maven spring RocketMQ Zabbix ubuntu centos kubesphere ffmpeg jenkins hbase JavaScript笔记 WordPress nginx Hadoop vuejs mongo SQL Server PostgreSQL SQLite ElasticSearch Spark netty zookeeper RabbitMQ ClickHoust cocos2d gradle tomcat Markdown MinIO react Hexo git intellij idea android studio svn C++ spdlog nodejs C WordPress 宝塔面板 vim shell logstash 软件渗透 NeoDB CSS3 HTML Lua笔记 数据算法 嵌入式 debian 红帽RHEL Neo4j