105成大資演第7題 ccmvic PTT批踢踢實業坊

105成大資演第7題

作者: ccmvic (Vic) 2019-02-21 13:34:21

https://i.imgur.com/Mg1XCxa.jpg
請問有人可以分享此題解答嗎？
感謝各位！

作者: Rioronja (想show幹話組) 2019-02-21 13:38:00

這個用Dijkstra但是relax的條件從相加變相乘好像要用bellmond-ford relax的條件從相加變相乘，而且要選比較大的 O(VE)下完成

作者: dumpling1234 (dumpling) 2019-02-21 14:00:00

取log 在做shortest path

作者: orzotz01 (Rixtons) 2019-02-21 15:44:00

https://i.imgur.com/NvHsEnf.jpg

作者: ccmvic (Vic) 2019-02-21 16:43:00

謝謝各位

作者: eric131204 (暗女巫) 2019-02-21 18:44:00

這題是directed，是不是要對s跟t各做一次dijkstra再取小的那條啊？

作者: Davidhu127 (船船_BTTO) 2019-02-22 22:30:00

不用做兩次取小的那條啊，題目是問find the path between u and v

繼續閱讀

[理工] 105成大線代是非題q5332159 [理工] 107成大電通（3）bochengchen [教育] 統計多元線性迴歸destroying [理工] 成大105計系(5)imadog [理工] Fibonacci heap觀念sooge [理工] 107成大電通greenyhi [理工] 成大 96離散排組magic83v [理工] 102成大計組AAQ8 [理工] AVL tree rotation觀念請問matt530 [理工] 107成大線代投影xinye0622

Contact Us: admin [ a t ] ucptt.com