离散复习资料之一（Dijkstra算法）
Dijkstra算法。
Dijkstra算法，也可以叫做标记法。它的原理是把所求目标点到达该点的最短路径标记起来，并且把每一个到达他的最短路径的点标记起来。就像（5,4），就是表示到达它的最短的距离是5.它是通过4到达的，类似于递归的思想。
先来看一个最短路问题：
最开始，建图。
在你们输入的集合中，我们先要把关系图做出来。比如说就是集合A={(a,b),(a,c),(b,c),(c,c)};
把这个集合变成图论的方式，也就是一个有向图。
有关系的我们就把它们之间用一根线连接起来。没有关系就不要去管他，
文章图片
这样我们就可以表示了A集合的有向图。
【离散复习资料之一（Dijkstra算法）】在进行标记权值，每一个路的长度表示一个权值，对于每一个边e，给定一个数W(e)，则它称为边e的权。把样的图也称为带权图。记住，A=
文章图片
比如这个简单的图。表示的含义以及权值。
最后就是路径的选择。下面我们来看几个图的选择与标记。
例在下面交通图中，权表示铁路的长度。求v0到v5的最短路径。属于S的点用方框表示，属于T的点用圆圈表示。
文章图片
下面我将根据图来进行说明，选择的就标记起，未选择的就是圆，选择的就是正方形。未选择的都是无穷大，
首先就是标记自己，因为自己到自己最近，距离为0，相应的可到达位置的距离改变，由无穷大变为可计算的距离。
文章图片
文章图片
文章图片
文章图片
到此也就一步一步的选择完了。也就是说v0到v5的最短距离为9.
还有一种标记方法就是程序设计中最常用的一种标记方法。
就是标识他的来路。采用两个数据去记录。
在程序设计中，采用数组和结构体，去完成标记，采用的思想就是并查集的思路和贪婪算法，他求出来的不一定是最短的，但是它是仅次于最优解的最优解。原因在于贪婪算法的缺点，他就是走最短的路，如果前面大，后面小的最短路的话就不可以了。
Dijkstra算法：
下面看一个题目进行简介。
一个总部和6个工地, 求从总部到各工地的最短路径
文章图片
标记的变量为2个，一个为“到你的最短距离的那点”，还有一个为“所求点到你的最短距离”，初始化，距离全为无穷大，出发到的点为S.未到达的点也为S（递归思想）
文章图片
下面开始Dijkstra算法：
文章图片
文章图片
未标记过的2，4，5，6，7标记过的1，3
文章图片
未标记过的3，4，5，6，7标记过的1，3，2
文章图片
未标记过的4，6，7标记过的1，3，2，5
文章图片
未标记过的4，7标记过的1，3，2，5，6
文章图片
未标记过的6，7标记过的1，3，2，5，4
文章图片
未标记过的 “空集”标记过的1，3，2，5，6，7
该方法的伪代码是采用两个集合的标记思路，一个为标记过的点集合，一个为未标记过的点集合。等到未标记点的集合为空集的时候，说明该算法结束。
相应的还有表格路径的表示方法如下：
文章图片
该方法到此结束，谢谢观看。如有不好的地方，其下方留言，我去一一改正！谢谢各位大佬观看。谢谢!
推荐阅读
- 话说先锋（与著名作家叶兆言对话之一）
- 九月胡杨叶正红(家乡十记之一)
- 离散之悟
- 你是个“头脑封闭”的人吗（（读《原则》有感之一））
- 给妈妈的十封信之一（妈妈，我爱你）
- 提笔醍醐之一
- 《可复制的领导力》读后感之一----学会倾听，提高效率
- 前台?番外篇之一
- 女子防身术基本要求之一
- 魔兽世界之一（备战）