圖的檢查S是G中的最短路徑樹（算法+正確性）

Question

G是僅具有正權重的連通無向圖。 S是最短路徑樹（不一定是G的SPT）。所以我設計一個算法來檢查圖S是圖的最短路徑樹G.

我的算法是一樣的東西....

運行Dijkstra算法（返回的圖，不是最短路徑）在G和S上檢查每個頂點的dist（v）值，如果全部相同，則S是G的最短路徑樹。我不知道這個算法是否有效，但是我不知道認爲這是合理的。如果這是真的，我如何證明它的正確性，如果沒有，反例會是非常有幫助的？

*我張貼這對CS交易所以及*

Answer 1

反證法：

假設S是G的最短路徑樹（具有相同的根目錄），並且存在一個頂點v，其中DIST（ⅴ）從Dijkstra算法不等於在其S.距離

允許檢查兩個選項：

1. Dijkstra在G上的算法的dist（v）大於它在S中的值。如果這樣，這意味着Dijkstra的算法是錯誤的，因爲這個頂點有一條較短的路徑。

2. Dijkstra算法對G的dist（v）小於S中的值 - 這意味着S不能成爲有效的最短路徑樹，因爲較短的路徑存在於頂點v，因此與我們的初始假設相矛盾。

Q.E.D.