从零开始学数据结构系列之第四章《迪杰斯特拉算法了解》

迪杰斯特拉（Dijkstra）算法

​   Dijkstra（迪杰斯特拉）算法是典型的单源最短路径算法，用于计算某个顶点到其他所有顶点的最短路径。Dijkstra（迪杰斯特拉）算法要求图中不存在负权边，即保证图中每条边的权重值为正。算法的基本思想是：从源点出发，每次选择离源点最近的一个顶点前进，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

优点：效率较高，时间复杂度为O(n^2)。

缺点：只能求一个顶点到所有顶点的最短路径。 （单源最短路）

原理

  1、先选定一个根结点，并选定一个数组，先确定未遍历前的初始距离，把距离最短的邻接结点选定为中间结点，并标记访问过，开始往下遍历，挨个访问那个中间结点的邻接结点。计算出根结点到中间结点+中间结点到新邻接结点的距离，作为新距离，对比新距离和旧距离，如果新距离大，则把新距离替换掉旧距离，否则不变。

  2、一轮访问结束后，从未标记的结点中选定距离最短的，把它作为中间结点，继续往下访问。若都标记过，则算法结束。

简单来说，就是求局部最优解，从而影响整体

它的主要特点是：以起始点为中心向外层层扩展（广度优先搜索思想）， 直到扩展到终点。

算法的基本思路

• 首先将起始节点的距离标记为0，其他节点的距离因为还不确定所以先需要标记为无穷大。
• 然后，在图中找到距离起始节点最近的节点，更新其相邻节点的距离，距离为从起始节点到该节点的距离加上该节点到相邻节点的距离。
• 不断循环此过程，直到所有节点都被访问过。

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解》
32【第三章】《平衡二叉树的旋转类型图文详解》
33【第三章】《平衡二叉树的旋转类型总结及总代码》
34【第三章】《哈夫曼树简单了解》
35【第三章】《哈夫曼树的构造方法》
36【第三章】《哈夫曼编码构造及代码》
37【第四章】《图的定义》
38【第四章】《图的基本概念和术语》
39【第四章】《图的存储结构》
40【第四章】《图的遍历之深度优先遍历》
41【第四章】《广度优先遍历BFS》
42【第四章】《图的遍历总代码》
43【第四章】《最小生成树概念》
44【第四章】《最小生成树的应用举例》
45【第四章】《prim算法（普里姆算法）详解》
46【第四章】《prim算法（普里姆算法）详解2》
47【第四章】《prim算法（普里姆算法）详解3》
48【第四章】《prim算法（普里姆算法）讲解汇总》
49【第四章】《prim算法（普里姆算法）代码讲解》
50【第四章】《prim算法（普里姆算法）总代码》
51【第四章】《克鲁斯卡尔算法思路介绍》
52【第四章】《克鲁斯卡尔算法步骤思路1》
53【第四章】《克鲁斯卡尔算法步骤思路2》
54【第四章】《克鲁斯卡尔算法应用场景-公交站问题》
55【第四章】《克鲁斯卡尔算法判断回路问题》
56【第四章】《克鲁斯卡尔算法步骤回顾》
57【第四章】《克鲁斯卡尔算法代码初始化详解》
58【第四章】《克鲁斯卡尔算法总代码详解》
59【第四章】《了解最短路径》