對于網(wǎng)絡(luò)中有負(fù)權(quán)弧時(shí)，可以使用哪種算法求取最短路？Dijkstra是目前最常用的最短路徑算法。它的使用條件是可以寫，并且圖中沒有負(fù)權(quán)重邊。SPFA算法是目前稀疏圖中最常用的最短路徑算法，不存在負(fù)環(huán)。你

對于網(wǎng)絡(luò)中有負(fù)權(quán)弧時(shí)，可以使用哪種算法求取最短路？

Dijkstra是目前最常用的最短路徑算法。它的使用條件是可以寫，并且圖中沒有負(fù)權(quán)重邊。SPFA算法是目前稀疏圖中最常用的最短路徑算法，不存在負(fù)環(huán)。你應(yīng)該會寫弗洛伊德。它是多源最短路徑最常用的算法。Dijkstra對程序ape有穩(wěn)定的性能。張勇對于OIer來說，只要不是稠密圖，就一定要寫SPFA，因?yàn)镾PFA在稀疏圖上太快了

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