表示一個圖，其中節點也是權重

Question

考慮一個圖表，它在每個節點上都有權重，而不是在兩個節點之間。因此，前往節點的成本將是該節點的權重。

1-我們如何表示這個圖？

2-是否有這種類型圖的最小生成路徑算法（或者我們可以修改現有算法）？

例如，考慮矩陣。從某個數字到另一個數字旅行時，什麼路徑會產生最小的總和？ （記住的圖形必須定向）

Answer 1

1. 如果不想調整現有的算法，並使用邊緣導向的方法，一個可以改變節點權重的邊權。對於節點v的每個傳入邊緣，都可以將v的權重保存到邊緣。這就是表示。

2. 好了，方法是1.現在很容易用衆所周知的算法，如MST。

您也可以將圖表表示爲希望並在節點上保持權重。該算法根本沒有使用Weight w = edge.weight();它將使用簡單的Weight w = edge.target().weight() 完成。不需要大的調整。

如果必須使用鄰接矩陣，則需要第二個具有節點權重的數組，並且在鄰接矩陣中只有0 - 對於無邊或1 - 對於邊。

希望能幫到