Dijkstra practice

Basic summary

 1  function Dijkstra(G, w, s)
 2     for each vertex v in V[G]        // 初始化
 3           d[v] := infinity           // 將各點的已知最短距離先設成無窮大
 4           previous[v] := undefined   // 各点的已知最短路径上的前趋都未知
 5     d[s] := 0                        // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
 6     S := empty set
 7     Q := set of all vertices
 8     while Q is not an empty set      // Dijkstra演算法主体
 9           u := Extract_Min(Q)
10           S.append(u)
11           for each edge outgoing from u as (u,v)
12                  if d[v] > d[u] + w(u,v)             // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
13                        d[v] := d[u] + w(u,v)         // 更新路径长度到更小的那个和值。
14                        previous[v] := u              // 记录前置节点

Extract_Min(Q)是提取节点使得这个节点到源节点的距离最小，每次都这么提取。需要计算所有节点的距离因此将Q设成所有节点，如果只需要计算特殊情形Q起始只有一个节点。用PriorityQueue实现res->正则很方便.

变形Dj

BFS,每次不是提取Min_Q节点,仅仅BFS，因为题目要求逐跳之内到达目标节点，层序遍历走到就走到，走不到就停止。每次判断条件仍然是距离向量。