平衡二叉樹中兩個節點之間的最短路徑如何受到路徑「權重」的影響？

Question

我正在使用Udacity進行在線介紹算法課程。

在最後的評估存在的問題如下：

在安德魯·戈德堡的採訪中描述的最短路徑甲骨文， 每個節點都有一個標籤，這是在其他一些節點的列表 網絡及其到這些節點的距離。這些列表具有 屬性是：

（1）對於任何一對網絡中的節點（X，Y）的，他們的列表將在 至少一個節點Z共同

（2）最短從x到y的路徑將通過z。給定一個平衡二叉樹圖G ，對圖進行預處理，爲每個節點創建這樣的 標籤。請注意，對於大小爲n的圖形，每個標籤 中列表的大小不應大於log n。

The full question can be found here.

給定一個平衡二叉樹的約束和提示，大小不應超過數N時，直觀看來，對於一個特定節點的標籤將包括其所有的父母（如果不是葉子，也可以選擇本身）。

然而，在這個問題一些額外的教練筆記補充說：

寫您的解決方案，加權圖形工作。請注意，測試 給出，所有的邊緣有一個權重 - 這並不是特別有趣。

所以我的問題是：

如何二叉樹兩個節點之間的最短路徑由路徑是否具有重量或不會受到影響？

當然，在二叉樹中，兩個節點之間的最短路徑是唯一的簡單路徑，並且不受任何權重的影響？ （除非權重可以是負數，並且路徑不必簡單，在這種情況下沒有最短路徑）

我的基本解決方案與問題中提供的簡單測試一起工作，但未能通過自動不給予反饋的平地機。

我顯然誤解的東西，但什麼......

Answer 1

好了，我想我最初的反應和明顯的答案是正確的：

正權不能影響最短路徑在二叉樹中的兩個節點之間。

在另一方面，權重明顯做影響二叉樹的最短「距離」兩個節點之間相比，計算簡單的跳數節點之間的「距離」。

這就是udacity指令得到的。 似乎這條使用加權二叉樹的指令只是簡單地啓用對依賴於使用標籤的代碼進行正確的自動分級來計算確切的最短'距離'（受重量影響），而不是最短路徑（節點列表）不是。

一旦我修改了我的算法，將其考慮在內並輸出正確的距離，它就通過了平地機。