文章詳情頁
java - 如何求多叉樹兩個任意節點的最短路徑呢？
瀏覽：274日期：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. 關于docker下的nginx壓力測試2. docker容器呢SSH為什么連不通呢？3. Docker for Mac 創建的dnsmasq容器連不上/不工作的問題4. mac里的docker如何命令行開啟呢？5. 關docker hub上有些鏡像的tag被標記““This image has vulnerabilities””6. nignx - docker內nginx 80端口被占用7. docker - 各位電腦上有多少個容器啊？容器一多，自己都搞混了，咋辦呢？8. angular.js使用$resource服務把數據存入mongodb的問題。9. docker 下面創建的IMAGE 他們的 ID 一樣？這個是怎么回事？？？？10. docker-compose 為何找不到配置文件？
排行榜
網公網安備 34170202000408號-皖ICP備2020019022號-1 sitemap
Copyright ￠ 2020-2025 Powered by http://www.b3g6.com V1.8 All Rights Reserved 技術支持：好吧啦網