文章詳情頁
java - 如何求多叉樹兩個任意節(jié)點的最短路徑呢？
瀏覽：190日期：2024-02-02 11:31:00
問題描述
每個節(jié)點的數(shù)據(jù)結(jié)構(gòu)是一個value ，和這個節(jié)點的所有子節(jié)點
問題解答
回答1：設(shè)有n個節(jié)點。
樹轉(zhuǎn)無向圖，然后用n次dijkstra、spfa等單源最短路算法或1次floyd多源最短路算法求任意兩節(jié)點的值。但是當(dāng)n比較大的話儲存值對內(nèi)存的開銷較大。
使樹成為有根樹，每個節(jié)點i儲存到根的距離di。查詢兩節(jié)點di,dj時，求兩節(jié)點的公共祖先dk，則d(i,j)=di+dj-dk*2。關(guān)于公共祖先可以參考tarjan算法。
回答2：當(dāng)成無向圖考慮Floyd算法.
標(biāo)簽：
java
上一條：java - 一個類的對象鎖只有一個，類鎖呢？下一條：java - c++學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)應(yīng)不應(yīng)該用stl實現(xiàn)？
相關(guān)文章：
1. java - 三位二進制表示8進制，四位二進制表示16進制，那么多少二進制表示10進制呢？2. docker 下面創(chuàng)建的IMAGE 他們的 ID 一樣？這個是怎么回事？？？？3. 如何用筆記本上的apache做微信開發(fā)的服務(wù)器4. angular.js - ionic2 瀏覽器跨域問題5. 【python|scapy】sprintf輸出時raw_string轉(zhuǎn)string6. python - Scrapy存在內(nèi)存泄漏的問題。7. docker-compose中volumes的問題8. android - rxjava merge 返回Object對象數(shù)據(jù)如何緩存9. mysql - 記得以前在哪里看過一個估算時間的網(wǎng)站10. java如何生成token？
排行榜
熱門標(biāo)簽
網(wǎng)公網(wǎng)安備