臨近期末，演算法老師留下一個斯坦福公開課的課堂思考題，說本題做出來的同學在期末成績上+5分，有這等好機會能爭取一下還是得爭取一下的，本題的思路并不難，主要是基于小頂堆對Dijkstra進行稍做改進，
該思考題如下：
In lecture we define the length of a path to be the sum of the lengths of its edges. Define the bottleneck of a path to be the maximum length of one of its edges. A mininum-bottleneck path between two vertices s and t is a path with bottleneck no larger than that of any other s?t path. Show how to modify Dijkstra’s algorithm to compute a minimum-bottleneck path between two given vertices. The running time should be 𝑂(𝑚log𝑛), as in lecture.
1 Dijkstra
在進行改進Dijkstra之前，我先進行回顧+總結一下Dijkstra，詳細請看：
回顧+總結：單源最短路Dijkstra
2. 用Dijkstra處理bottleneck與mininum bottleneck問題
下面結合小頂堆及Dijkstra的思想進行處理mininum bottleneck問題，詳細請看：
基于單源最短路Dijkstra解決mininum bottleneck問題
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/239663.html
標籤：其他
上一篇：2020TI杯全國大學生電子設計大賽F題解決方案視覺部分
下一篇：Verilog之計數器設計實作