【第二十六天 - Dijkstra 介绍】

Q1. Dijkstra 是什麽?

• 一种利用 Dynamic Programming ，与 Floyd-Warshall 一样，是求 Graph 中两点之间最短路径的演算法。
• Floyd-Warshall 是计算「每一个点」到其他点的最短路径
• Dijkstra 是计算「某一个点」到其他点的最短距离

条件限制：

Dijkstra 适用的 graph 中，不可以有负权重的边。

流程：

1. 选择一个起点，以下图为例，我们假设起点为第 0 点

2. 将起点「直接相邻」的节点权重视为最短路径长，其他结点的路径长则视为无限大。
   

3. 选取距离最近的节点，如 0→1 与 0→2 两条路径，选择第1点目前路径较短的开始看，由於不可能有其他路径比当前的更短了（因为图中无负权重，要从其他节点过来一定会更远），我们可以确定此距离就是真正的最短距离。

4. 从当前选取的节点(第1点)出发前往其他节点(相邻的点有2与3)，如果能比已知的路径长更短(0→2原本纪录为4，0→1→2=3，选最短路径的3)，就更新已知的路径长；如果需要知道最短路径的确切节点，可以在更新时一并纪录前一节点。

5. 反覆 3 ~ 5 ，直到所有节点都找到最短路径。
   

参考资料：https://ithelp.ithome.com.tw/articles/10209593

参考资料：https://ithelp.ithome.com.tw/articles/10238059

Q2. 学会 Dijkstra 概念可以做什麽 ?

可以求 Graph 中两点之间的最短路径。

Lab. 明天要解的题目：1514. Path with Maximum Probability

• 题目连结：https://leetcode.com/problems/path-with-maximum-probability/

• 题目叙述

  • 题目给 n 个节点，并且 edges 会储存从 a 点到 b 点的边(无向图)，succProb 储存 a 点到 b 点的「成功概率」
  • 计算从 start 点到 end 点的最大成功机率，若无法抵达，则回传0
    

• 测资的 Input/Output

  • 如范例1，第0点抵达第2点有两种走法： 0→1→2 与 0→2
  • 需要回传 start → end 点最高成功机率： max(0→1→2 ,0→2) = max(0.5*0.5,0.2) = 0.25
    
    

• 题目的条件

  • 会有 2~10000 个点
  • start 与 end 介於 0~10000 间
  • start 与 end 不会是同一个点
  • edges 中的点，会是介於 0~10000间
  • edges 所记录的 a 点到 b 点不会是同一个点
  • 「edges 纪录的边长」会与 「succProb 的成功机率」数量相同，并介於 0~20000 间
  • succProb 成功机率介於 0~1 之间
  • 两个点之间，最多只有一条边