文件列表:

Dijkstra_mininum_bottleneck.py (5002, 2023-01-02)
Example.png (46891, 2023-01-02)
data_example (243, 2023-01-02)

# Dijkstra_mininum_bottleneck ## 1.Question 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 Dijkstras algorithm to compute a minimum-bottleneck path between two given vertices. The running time should be ‘(‘log‘), as in lecture. ## 2.Definition - 2.1 è·éè·èé’ - 2.2 è·bottleneckè·è褧length - 2.3 S-T¤é—mininum-bottleneckè·S-Té—‰°bottleneckè·é - 2.4 è±O(mlogn) ## 3.Solution #### 3.1 —é—¤é DijkstraO(mn)---> O(n^2) --->O(mlogn)(…’)¤éèèO(mlogn)¤é¤èèè餖èéè…°é #### 3.2 bottlenecké è·bottleneckè·è褧length¨èèèè¨éè°è¤§ #### 3.3 mini_bottlenecké S-T¤é—mininum-bottleneckè·S-Té—‰°bottleneckè·é¨—°¤§¤–èè°±¨“‰¤§èè鉖° …… ‘‘,‘‘‰’‘‘‘‘–‘‘(‘)=min(‘‘‘–‘‘(‘),max(‘‘‘–‘‘(‘),‘¤‘’‘–‘”‘(‘,‘))) #### 3.4 Dijkstra ‘‘,‘‘‰’‘‘‘‘–‘(‘)=min(‘‘‘–‘‘(‘),‘‘‘–‘‘(‘)+‘¤‘’‘–‘”‘(‘,‘)) #### 3.5 Dijkstra_mininum_bottleneck ‘‘,‘‘‰’‘‘‘‘–‘‘(‘)=min(‘‘‘–‘‘(‘),max(‘‘‘–‘‘(‘),‘¤‘’‘–‘”‘(‘,‘))) - 3.5.1 bottleneck = max(‘‘‘–‘‘(‘),‘¤‘’‘–‘”‘(‘,‘)) è…–°bottleneck°è·é - 3.5.2 min(‘‘‘–‘‘(‘), bottleneck) è°bottleneck°mininum_bottleneck;¤—‘‘‘–‘‘(‘)è°“‰¤èé—bottleneckéè–èè°°è ## 4.Data Example 6 7 1 2 3 2 3 2 1 3 30 3 4 20 4 5 30 3 5 6 5 6 1 ## Conference https://blog.csdn.net/weixin_41297324/article/details/111506679 https://github.com/LSijing/Algorithms-Stanford https://blog.asarkar.com/algorithms-design-analysis/hw-5-opt/ https://github.com/aleksandrpak/solutions/tree/master/coursera/algorithms_design_and_analysis_part_1

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：