最短路徑中使用的邊沿

-1

我剛學過「最短路徑算法」。現在我想知道最短路徑圖是怎麼樣的。最短路徑中使用的邊沿

I.e.我在節點N，我從這裏運行最短路徑算法。因此，如果我使用最短路徑算法中使用的邊來製作圖，圖的外觀如何？

我想這個圖形是樹根，在N，根與其他節點之間的路徑最短。

2016-10-19 DreamWorks

是的，你說得對，圖中基本上形成了一個樹（稱爲生成樹）與N叉 –

，我認爲你的假設大多成立。然而，對於具有相同成本的多條路徑的圖形，對於具有負循環的圖形，圖形可能會變得更加複雜。 – Binus

基本上，如果你看到由最短路徑構成的子圖，是的，它將是一棵樹，實際上是一棵生成樹。它也有類似的特性。看到我發佈的鏈接。

給定連接，無向圖G中，在頂點v爲根的最短路徑樹是G的生成樹T，使得從根v到任何其他頂點u T中的路徑距離是從v G中最短路徑到u

參考

shortest-path-tree

Spanning Tree。

shortest ptah tree.pdf

2016-10-19 06:16:56 v78

當然，但這不是一個答案，這只是你丟棄的兩個鏈接 – Rerito

@Rerito，他接受了我的答案。如果不認爲這是不夠的，你能否通過更好的方式教我如何去做。 – v78

請參閱[此鏈接]（http://meta.stackexchange.com/q/225370/284827）。 –

回答