文章詳情頁
java - 如何求多叉樹兩個任意節點的最短路徑呢？
瀏覽：195日期：2024-02-02 11:31:00
問題描述
每個節點的數據結構是一個value ，和這個節點的所有子節點
問題解答
回答1：設有n個節點。
樹轉無向圖，然后用n次dijkstra、spfa等單源最短路算法或1次floyd多源最短路算法求任意兩節點的值。但是當n比較大的話儲存值對內存的開銷較大。
使樹成為有根樹，每個節點i儲存到根的距離di。查詢兩節點di,dj時，求兩節點的公共祖先dk，則d(i,j)=di+dj-dk*2。關于公共祖先可以參考tarjan算法。
回答2：當成無向圖考慮Floyd算法.
標簽：
java
相關文章：
1. javascript - vue提示語法錯誤，請問錯誤在哪？2. css - 移動端 oppo 手機之 Border-radius3. 淺談vue生命周期共有幾個階段？分別是什么？4. index.php錯誤，求指點5. java - web端百度網盤的一個操作為什么要分兩次請求服務器, 有什么好處嗎6. javascript - vue.js如何遞歸渲染組件.7. python - 抓包只抓到json，真實的地址卻找不到8. javascript - 為什么我的animation-fill-mode 設置不生效9. angular.js - angularjs中添加高德地圖API，地圖顯示不正常，控制臺報錯，何解？10. html - JavaScript的Dom操作如何改變子元素的文本內容
排行榜
網公網安備