我們是否可以將Bellman ford算法應用於無向圖

我知道Bellman-Ford算法適用於有向圖，但僅適用於Info我想知道它是否適用於無向圖？由於使用Un-directed圖，它將無法檢測週期，因爲平行邊將被視爲Cycles !!。請澄清。我們是否可以將Bellman ford算法應用於無向圖

看看[this]（http://stackoverflow.com/questions/14538403/shortest-path-algorithms-for-undirected-graph）之一。 – Nik 2013-02-09 05:57:38

事實上，任何無向圖都是一個有向圖。

你只需要指定任何邊{u，v}兩次（u，v）和（v，u）。

但請不要忘記，這也意味着任何具有負重量的邊緣都將被視爲一個循環。由於Bellman-Ford算法僅適用於不含任何具有負權重的循環的圖形，這實際上意味着您的無定向圖形不得包含具有負權重的任何邊緣。

如果它使用貝爾曼福特不是很好。

2013-02-11 00:59:27 mikyra

要詳細說明這一點 - 由於圖必須只有非負邊，這意味着您可能只想使用Dijkstra算法，因爲它漸近地更快。 – templatetypedef 2013-02-11 01:03:16

我有同樣的疑問。感謝您的澄清。 – whitehat 2015-07-15 19:24:59

回答