文章詳情頁
java - 如何求多叉樹兩個任意節點的最短路徑呢？
瀏覽：158日期：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. python bottle跑起來以后,定時執行的任務為什么每次都重復(多)執行一次?2. python - 爬蟲模擬登錄后，爬取csdn后臺文章列表遇到的問題3. html5 - HTML代碼中的文字亂碼是怎么回事？4. 視頻文件不能播放，怎么辦？5. javascript - vue2如何獲取v-model變量名6. javascript - 求幫助 , ATOM不顯示界面!!!!7. mysql - 分庫分表、分區、讀寫分離 這些都是用在什么場景下 ，會帶來哪些效率或者其他方面的好處8. javascript - 為什么在谷歌控制臺 輸出1的時候，輸出的1立馬就不見了9. javascript - angular使從elastichearch中取出的文本高亮顯示，如圖所示10. javascript - ios返回不執行js怎么解決？
排行榜
網公網安備