图文解析 | Dijkstra单源最短路径算法
给定 加权有向图 G=(V,E,W)，每条边的权值w为 非负数 ，表示两个顶点间的距离。
源点s∈V。
求：从s出发到其他各个顶点的最短路径。
如上图所示，以1为源点，计算到其余各个顶点的最短距离（我已用红线标出）。下面列出了最终解：
S集合 ：当从s到x（x ∈V ）的最短路径找到时，则x ∈S。当所有顶点都进入S集合时，算法结束。
初始：S=｛s｝，当S=V时算法结束。
从s到u相对于S的最短路径 ：指从s到u且仅经过S中顶点的最短路径。
dist[u]:从s到u相对于S的最短路径长度
short[u]:从s到u最短路径的长度（算法最终解）
dist[u] ≥ short[u]
Dijkstra算法采用贪心算法模式，算法过程就是通过计算dist[u],不断扩充S集合，同时dist[u]会不断优化改善，直到dist[u] = short[u]，并将其放到S中，当所有顶点都放入S集合时，算法结束。
输入：加权有向图G=(V,E,W)
V={1,2,…,n}, s=1
输出：从s到每个顶点的最短路径
输入：G=(V,E,W)，源点1
V={1,2,3,4,5,6}
初始S集合只有1，计算直接从1能到达的顶点的距离，其他不能从1号顶点直接到达的顶点都记为无穷大。此时从dist[u]里找出最短距离的顶点（6号），并将其放进S集合。
S={1}
dist[1] = 0
dist[2] = 10
dist[6 ] = 3
dist[3] = ∞
dist[4] = ∞
dist[5] = ∞
当把6号顶点放进S集合后，经由6号顶点出发到达的顶点的最短距离可能会被优化更新，因为该算法的思想很“贪心”，谁更短我要谁！比如1-6-2要比1-2距离更短，所以dist[2]被更新为5，从专业术语上讲，这个“更新”过程叫做松弛，其他点同理。然后从dist[u]里找出最短的路径的那个顶点（5号），并放进S集合里。
S={1,6}
dist[1] = 0
dist[6] = 3
dist[2] = 5
dist[4] = 9
dist[5] = 4
dist[3] = ∞
后面的操作步骤其实就是重复上面的操作。即当S集合里有个新的顶点后，就可能会更新其他点的最短距离，更新一遍后，找出当前最短距离的dist[u]，并将该顶点放进S集合。后面不重复阐述。
S={1,6,5}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = ∞
S={1,6,5,2}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
S={1,6,5,2,4}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
S={1,6,5,2,4,3}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
当有向图中的所有顶点都进入了S集合后，算法结束，此时的dist[u]的值其实就是最初我们找出的那个最终解short[u]，所以，算法结束时，dist[u]=short[u],得到最终解。
迪杰斯特拉(Dijkstra)算法详解
Dijkstra算法设置一个集合S记录已求得的最短路径的顶点，初始时把源点v0放入S，集合S每并入一个新顶点vi，都要修改源点v0到集合V-S中顶点当前的最短路径长度值。
本例基于邻接矩阵存储的图。
在构造的过程中要设置三个辅助数组：
假设从顶点0出发，即v0=0，集合S最初只包含顶点0，邻接矩阵 edge[][] 表示带权有向图， edge[i][j] 表示有向边i,j的权值，若不存在有向边i,j，则 edge[i][j] 为∞。
Dijkstra算法的步骤如下：
顶点数：5，弧数：10
顶点编号：A B C D E
邻接矩阵：
参考结果：
Dijkstra算法流程图
定义G=(V,E)，定义集合S存放已经找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点，即有T=V-S
Dijkstra算法描述如下：
(1) 假设用带权的邻接矩阵edges来表示带权有向图，edges[i][j]表示弧Vi, Vj上的权值。若Vi, Vj不存在则置edges[i][j]=∞（计算机上用一个允许的最大值代替）。S为已经找到的从Vs出发的最短路径的终点集合，它初始化为空集。那么，从Vs出发到图上其余各顶点（终点）Vi可能达到的最短路径长度的初值为：D[i]=deges[s][i] Vi∈V
(2) 选择Vj，使得D[j]=Min{D[i]|Vi∈V-S}，Vj就是当前求得的一条从Vs出发的最短路径的终点。令S=S∪{Vj}
(3) 修改从Vs出发到集合V-S上任一顶点Vk可达的最短路径长度。如果D[j]+edges[j][k]D[k]则修改D[k]为D[k]=D[j]+edges[j][k]
重复操作(2)(3)共n-1次。由此求得从Vs到图上其余各顶点的最短路径。
图遍历算法之最短路径Dijkstra算法
最短路径问题是图论研究中一个经典算法问题，旨在寻找图中两节点或单个节点到其他节点之间的最短路径。根据问题的不同，算法的具体形式包括：
常用的最短路径算法包括：Dijkstra算法，A 算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改进版本），Floyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文将重点介绍Dijkstra算法的原理以及实现。
Dijkstra算法，翻译作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出，用于解决赋权有向图的 单源最短路径问题 。所谓单源最短路径问题是指确定起点，寻找该节点到图中任意节点的最短路径，算法可用于寻找两个城市中的最短路径或是解决著名的旅行商问题。
问题描述 ：在无向图 中， 为图节点的集合， 为节点之间连线边的集合。假设每条边 的权重为 ，找到由顶点 到其余各个节点的最短路径（单源最短路径）。
为带权无向图，图中顶点 分为两组，第一组为已求出最短路径的顶点集合（用 表示）。初始时 只有源点，当求得一条最短路径时，便将新增顶点添加进 ，直到所有顶点加入 中，算法结束。第二组为未确定最短路径顶点集合（用 表示），随着 中顶点增加， 中顶点逐渐减少。
以下图为例，对Dijkstra算法的工作流程进行演示（以顶点 为起点）：
注：
01） 是已计算出最短路径的顶点集合；
02） 是未计算出最短路径的顶点集合；
03） 表示顶点 到顶点 的最短距离为3
第1步 ：选取顶点 添加进
第2步 ：选取顶点 添加进 ，更新 中顶点最短距离
第3步 ：选取顶点 添加进 ，更新 中顶点最短距离
第4步 ：选取顶点 添加进 ，更新 中顶点最短距离
第5步 ：选取顶点 添加进 ，更新 中顶点最短距离
第6步 ：选取顶点 添加进 ，更新 中顶点最短距离
第7步 ：选取顶点 添加进 ，更新 中顶点最短距离
示例：node编号1-7分别代表A,B,C,D,E,F,G
(s.paths - shortest.paths(g, algorithm = "dijkstra"))输出结果：
(s.paths - shortest.paths(g,4, algorithm = "dijkstra"))输出结果：
示例：
找到D（4）到G（7）的最短路径：
[1] 维基百科，最短路径问题： ；
[2]CSDN，Dijkstra算法原理： ;
[3]RDocumentation: ;
[4]RDocumentation: ;
[5]Pypi:
最短路径算法（Dijkstra）
Dijkstra（ 迪科斯特拉 ）算法是用来解决单源最短路径的算法，要求路径权值非负数。该算法利用了深度优先搜索和贪心的算法。
下面是一个有权图，求从A到各个节点的最短路径。
第1步：从A点出发，判断每个点到A点的路径（如果该点不能直连A点则距离值为无穷大，如果该点能和A直连则是当前的权值），计算完之后把A点上色，结果如下图:
第2步：从除A点之外的点查找到距离A点最近的点C，从C点出发查找其邻近的节点（除去已上色的点），并重新计算C点的邻近点距离A点的值，如图中B点，若新值（C点到A点的值+C点到该点的路径）小于原值，则将值更新为5，同理更新D、E点。同时将C标记为已经处理过，如图所示涂色。
第3步：从上色的节点中查找距离A最近的B点，重复第3步操作。
第4步： 重复第3步，2步，直到所有的节点都上色。
最后就算出了从A点到所有点的最短距离。
leetcode 743题
【数据结构】最短路径之迪杰斯特拉(Dijkstra)算法与弗洛伊德(Floyd)算法
迪杰斯特拉(Dijkstra)算法核心： 按照路径长度递增的次序产生最短路径。
迪杰斯特拉(Dijkstra)算法步骤：（求图中v0到v8的最短路径）并非一下子求出v0到v8的最短路径，而是 一步一步求出它们之间顶点的最短路径 ，过过程中都是 基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得出源点与终点的最短路径 。
弗洛伊德(Floyd)算法是一个经典的 动态规划算法 。