文章詳情頁
java - 如何求多叉樹兩個任意節(jié)點的最短路徑呢？
瀏覽：163日期：2024-02-02 11:31:00
問題描述
每個節(jié)點的數(shù)據(jù)結構是一個value ，和這個節(jié)點的所有子節(jié)點
問題解答
回答1：設有n個節(jié)點。
樹轉(zhuǎn)無向圖，然后用n次dijkstra、spfa等單源最短路算法或1次floyd多源最短路算法求任意兩節(jié)點的值。但是當n比較大的話儲存值對內(nèi)存的開銷較大。
使樹成為有根樹，每個節(jié)點i儲存到根的距離di。查詢兩節(jié)點di,dj時，求兩節(jié)點的公共祖先dk，則d(i,j)=di+dj-dk*2。關于公共祖先可以參考tarjan算法。
回答2：當成無向圖考慮Floyd算法.
標簽：
java
相關文章：
1. java - public <T> T findOne(T record) 這是什么意思2. css - 關于ul的布局3. javascript - 前端開發(fā) 本地靜態(tài)文件頻繁修改，預覽時的緩存怎么解決？4. android - 優(yōu)酷的安卓及蘋果app還在使用flash技術嗎？5. java - new + 類名，一定需要申明一個對象嗎？6. docker不顯示端口映射呢？7. mysql數(shù)據(jù)庫每次查詢是一條線程嗎？8. python - linux怎么在每天的凌晨2點執(zhí)行一次這個log.py文件9. 如何分別在Windows下用Winform項模板+C#，在MacOSX下用Cocos Application項目模板+Objective-C實現(xiàn)一個制作游戲的空的黑窗口？10. 小程序怎么加外鏈，語句怎么寫！求救新手，開文檔沒發(fā)現(xiàn)
排行榜
熱門標簽
網(wǎng)公網(wǎng)安備