简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)
java - 如何求多叉树两个任意节点的最短路径呢？
ringa_lee
ringa_lee 2017-04-18 10:48:59
0
2
602

每个节点的数据结构是一个value ，和这个节点的所有子节点

ringa_lee
ringa_lee

ringa_lee

全部回覆(2)
Ty80
Ty802017-04-18 10:50:59 2樓

設有n個節點。

  1. 樹轉無向圖，再用n次dijkstra、spfa等單源最短路演算法或1次floyd多源最短路演算法求任兩節點的值。但是當n比較大的話儲存值對記憶體的開銷較大。

  2. 使樹成為有根樹，每個節點i儲存到根的距離di。查詢兩節點di,dj時，求兩個節點的公共祖先dk，則d(i,j)=di+dj-dk*2。關於公共祖先可以參考tarjan演算法。

點贊 +0
新增回覆
小葫芦
小葫芦2017-04-18 10:50:59 1樓

當成無向圖考慮Floyd演算法.

點贊 +0
新增回覆
熱門專題
更多>
熱門文章
熱門教學
更多>
相關教學
熱門推薦
最新課程
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網：公益線上PHP培訓，幫助PHP學習者快速成長！