Dikstra

Dikstra的概念是BFS ,只是把BFS的Queue換成MInheap, 每次去取最小執行去找到最短路徑的演算法,是一種Greedy的演算法

Step:

  1. 會需要一個min_heap和done_set
  2. 把起始值放進去
  3. 先去pop, pop出來的東西會是距離和node
  4. 檢查點是否在done_set內
  5. 從node去拜訪鄰居 把結果存到minHeap
  6. 檢查鄰居是否完成 (有沒有在doneset內)
  7. 0完成後用一個set記起來,防止minHeap內還有0
  8. 重複第3點之後的動作

505. The Maze II

743. Network Delay Time

1293. Shortest Path in a Grid with Obstacles Elimination

1631. Path With Minimum Effort

1102. Path With Maximum Minimum Value

1091. Shortest Path in Binary Matrix