dijstra算法的使用需要哪些條件？Dijstra算法一般用于權(quán)值大于或等于零的有向或無向圖來求解單源最短路徑問題如果權(quán)值小于零，則不能保證正確解如果是無權(quán)值圖，直接使用廣度優(yōu)先搜索Dijstra的

dijstra算法的使用需要哪些條件？

Dijstra算法一般用于權(quán)值大于或等于零的有向或無向圖來求解單源最短路徑問題

如果權(quán)值小于零，則不能保證正確解

如果是無權(quán)值圖，直接使用廣度優(yōu)先搜索

Dijstra的標(biāo)準(zhǔn)實現(xiàn)是基于有向圖的。對于無向圖，所有邊都可以看作是雙向連通的有向邊，并轉(zhuǎn)化為有向圖

a*算法是一種啟發(fā)式搜索，適用于點到點的最短路徑。Floyd是單源單匯情況下的一種動態(tài)規(guī)劃方法，它能在任意兩點之間找到最短路徑。Dijkstra是一種貪心算法，對于所謂的單源最短路徑算法，它能找到從一點到所有其他點的最短路徑，F(xiàn)loyd是O（n^3），Dijkstra是O（n^2），當(dāng)然就時間復(fù)雜度而言，結(jié)果是一樣的，都是最短路徑，但應(yīng)用場合和時空開銷不同

優(yōu)點：算法簡潔，能得到最優(yōu)解，缺點：效率低（特別是有時不需要最優(yōu)解），運算空間大