文章詳情頁
java - 如何求多叉樹兩個任意節點的最短路徑呢？
瀏覽：171日期：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. 在mybatis使用mysql的ON DUPLICATE KEY UPDATE語法實現存在即更新應該使用哪個標簽?2. 哭遼 求大佬解答 控制器的join方法怎么轉模型方法3. mysql儲存json錯誤4. mysql - 怎么生成這個sql表？5. mysql - 數據庫表中，兩個表互為外鍵參考如何解決6. Navicat for mysql 中以json格式儲存的數據存在大量反斜杠，如何去除？7. sql語句 - 如何在mysql中批量添加用戶？8. mysql - 表名稱前綴到底有啥用？9. 編輯成功不顯示彈窗10. 怎么php怎么通過數組顯示sql查詢結果呢，查詢結果有多條，如圖。
排行榜
網公網安備