文章詳情頁
java - 如何求多叉樹兩個任意節點的最短路徑呢？
瀏覽：172日期：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 - 關于定時器 與 防止連續點擊 問題2. javascript - 求助關于js正則問題3. objective-c - ios百度地圖定位問題4. javascript - 求助這種功能有什么好點的插件？5. javascript - js 有什么優雅的辦法實現在同時打開的兩個標簽頁間相互通信？6. 為何 localStorage、sessionStorage 屬于html5的范疇，但是為何 IE8卻支持？7. html5 - rudy編譯sass的時候有中文報錯8. html - css 如何添加這種邊框?9. javascript - node.js服務端渲染解疑10. 微信開放平臺 - Android調用微信分享不顯示
排行榜
網公網安備