最短路徑樹索賠（圖）

Question

索賠：如果圖中的所有邊權重是不同的，則存在唯一的最短路徑樹。要麼給出一個令人信服的論點，即聲稱是真實的，要麼給出反例。

Answer 1

如果你有MST再有就是從每兩個頂點，這使得最短路徑樹無謂的唯一路徑。我假定你的意思是結果是一個MST。但是，這不是事實。最短路徑樹與同一圖形的最小生成樹不同，即使是同一個根也是如此。 植根於頂點的最短路徑樹v通常是將Dijkstra算法應用於v以上的結果。

一般來說，除非給出嚴格的要求（比如新的權重等於舊的+1），否則很難相信樹對圖的唯一性。 @rici給出了一個有polytree結構的反例。這是另一個無向圖的反例。兩棵樹都是根植於A的最短路徑樹。請注意：

• 儘管兩者都是最短路徑樹，但它們的總成本不同。
• 兩者都是生成樹，但它們都不是最小值。

Answer 2

如果我理解這個問題，正確：