Dikstra的概念是BFS ,只是把BFS的Queue換成MInheap, 每次去取最小執行去找到最短路徑的演算法,是一種Greedy的演算法
Step:
- 會需要一個min_heap和done_set
- 把起始值放進去
- 先去pop, pop出來的東西會是距離和node
- 檢查點是否在done_set內
- 從node去拜訪鄰居 把結果存到minHeap
- 檢查鄰居是否完成 (有沒有在doneset內)
- 0完成後用一個set記起來,防止minHeap內還有0
- 重複第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
