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

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

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

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

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

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

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

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