在解决带权有向图的最短路径中，Dijkstra算法(迪杰斯特拉)用于解决单源有向图的最短路径问题。我们把一张有向图的起始称为源点，结束称为终点，最短路径就是从源点到终点所经历的最小权值之和。本文将介绍Dijkstra算法的原理和实用案例。
（PS.如果你是为了今天的每日一题来的，那么你找对地方了，因为本人也是特地来恶补的）
Dijkstra算法的主要思想是贪心，每次将选中距离源点最近的点，并不断更新。为实现这个目的，我们维护一个dist[]数组和一个visited[]数组，并规定：
1、图的邻接矩阵中，若a无指向b的边，将其距离视为∞(为显示直观并且防止溢出，可设为MAX=INT_MAX/2)
2、dist[i]数组表示目前更新到的i位置距离源点的最短距离。
3、visited[i]==1表示i到源点的距离已是最近，无法再更新。
我们进行以下步骤：
1、初始化邻接矩阵、dist数组和visited数组
2、扫描dist数组，找出距离源点最近的节点i（若visited[i]=1，该节点不进行比较）
3、i距离源点的最短距离已被找到，将visited[i]设为1
4、找出i指向的节点并更新他们与源点的最短距离。
5、重复2~4
请看下面这个例子：
设源点为A，初始化阶段把源点dist[0]初始化为0，其余为MAX。(源点到源点的最短距离为0，其他点还未扫描到，可暂时用MAX初始化。同时，在扫描结束后，也可以依据是否有节点距离源点MAX，判断该有向图是否存在无法到达的节点。)
节点
A
B
C
D
E
F
dist
0
MAX
MAX
MAX
MAX
MAX
visited
0
0
0
0
0
0
（1）第一次扫描：
扫描dist数组，距离源点最近的节点为A，因此A到源点的最短距离为0。
将visited[ A ]设为1。
将其余点设为min (dist[ A ]+G[ A ][i] ,dist[i])
(A到源点的最短距离已经求出，更新A直接指向的点i到源点的距离，即dist[A]+G[A][i]，该点有可能比原本的dist[i]大，取最小)
节点
A
B
C
D
E
F
dist
0
1
5
MAX
MAX
MAX
visited
1
0
0
0
0
0
（2）第二次扫描：
扫描dist数组，与源点距离最近的点为B（注意:visited[A]已被设为1，表示已找到最短距离无法再更新，因此A不被扫描到。）
将visited[ B ]设为1。
将其余点设为min (dist[ B ]+G[ B ][i] ,dist[i])
这里dist[C]的值被更新，因为A->B->C的距离比A->C的距离短。
节点
A
B
C
D
E
F
dist
0
1
4
3
MAX
MAX
visited
1
1
0
0
0
0
（3）第三次扫描
扫描dist数组，与源点距离最近的点为D（注意:visited[i]已被设为1，表示已找到最短距离无法再更新，因此i不被扫描到。）
将visited[ D ]设为1。
将其余点设为min (dist[ D ]+G[ D ][i] ,dist[i])
节点
A
B
C
D
E
F
dist
0
1
4
3
4
7
visited
1
1
0
1
0
0
（4）第四次扫描
扫描dist数组，与源点距离最近的点为E（注意:visited[i]已被设为1，表示已找到最短距离无法再更新，因此i不被扫描到。）
将visited[ E ]设为1。
将其余点设为min (dist[ E ]+G[ E ][i] ,dist[i])
节点
A
B
C
D
E
F
dist
0
1
4
3
4
7
visited
1
1
0
1
1
0
（5）第五次扫描
扫描dist数组，与源点距离最近的点为C（注意:visited[i]已被设为1，表示已找到最短距离无法再更新，因此i不被扫描到。）
将visited[ C ]设为1。
将其余点设为min (dist[ C ]+G[ C ][i] ,dist[i])
节点
A
B
C
D
E
F
dist
0
1
4
3
4
7
visited
1
1
1
1
1
0
（6）第六次扫描
扫描dist数组，与源点距离最近的点为F（注意:visited[i]已被设为1，表示已找到最短距离无法再更新，因此i不被扫描到。）
将visited[ F ]设为1。
将其余点设为min (dist[ F ]+G[ F ][i] ,dist[i])
节点
A
B
C
D
E
F
dist
0
1
4
3
4
7
visited
1
1
1
1
1
1
（7）第七次扫描
所有visited均被设为1，表示所有节点均已找到与源点的最短距离。
若有向图中有的节点无法到达：
节点
A
B
C
D
E
F
G
dist
0
1
4
3
4
7
MAX
visited
1
1
1
1
1
1
0
此时我们已经把能到达的点的最短路径找出来了，按之前的步骤扫描dist数组，发现距离源点最近的节点为G，（前面已经说过了，visited数组限制了A~F不进行此次扫描的比较）。而dist[G]的值为MAX，即我们初始化的“无限大”，因此判断存在无法到达的节点。
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例1：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
示例 2：
输入：times = [[1,2,1]], n = 2, k = 1
输出：1
示例 3：
输入：times = [[1,2,1]], n = 2, k = 2
输出：-1
题目来源于：743. 网络延迟时间 - 力扣（LeetCode）