Medium
双周赛 #27 和 周赛 #193 碰到了两道图的题目，课程安排 IV 学习了，Floyd算法（多源最短路径算法）。同时接触到了Dijkstra 同源最短路径算法，但是一直没有时间学习。通过这道题，边学习边尝试写一下。
Dijkstra算法学习
有关Dijkstra的解释，看完以下的文章就理解了，讲的非常清晰
图的问题，无论是使用什么算法，基本上我们都需要构造邻接图或邻接矩阵。看完下面的文章，应该可以掌握了
新手总结
dis数组中距离当前点最近的点开始，不断更新距离值，这个操作叫做松弛dis数组时，说明我们找到一条更近的路径，我们就需要将这个节点更新到path数组当中。具体可以查阅Disjkstra算法学习的第一个链接。回到本题
-1以上，知识储备已就位，尝试写一下代码，AC！
python3
class Solution:
# 根据当前节点，选出距离当前节点最近的节点
def closestNode(self, visited, node, dis):
temp = math.inf
cur_node = 0
for n in range(len(dis)):
if n not in visited and n != 0 and n != node:
if dis[n] < temp:
temp = dis[n]
cur_node = n
return cur_node
def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
# 构造邻接表/邻接矩阵
graph = [[math.inf for _ in range(N+1)] for _ in range(N+1)] # 多个(0,0),这样使符合题目中节点值等于下标
for t in times:
graph[t[0]][t[1]] = t[2]
for n in range(N+1):
graph[n][n] = 0
visited = set()
dis = [math.inf] * (N + 1) # 记录节点的距离，index代表数字，多个0
for n in range(N+1):
dis[n] = graph[K][n]
dis[0] = -1
dis[K] = 0
cur_node = K
for _ in range(N+1):
for d in range(1, len(dis)):
if (dis[cur_node] + graph[cur_node][d]) < dis[d]:
dis[d] = dis[cur_node] + graph[cur_node][d]
visited.add(cur_node)
cur_node = self.closestNode(visited, cur_node, dis)
result = max(dis)
return result if result < math.inf else -1