尋找最短路徑時(shí)，是BFS和Dijkstra的算法有什么區(qū)別？Dijkstra算法的功能可以在Dijkstra算法的基礎(chǔ)上做一些修改來擴(kuò)展。例如，有時(shí)我們希望在找到最短路徑的基礎(chǔ)上列出一些子短路徑。為了

尋找最短路徑時(shí)，是BFS和Dijkstra的算法有什么區(qū)別？

Dijkstra算法的功能可以在Dijkstra算法的基礎(chǔ)上做一些修改來擴(kuò)展。

例如，有時(shí)我們希望在找到最短路徑的基礎(chǔ)上列出一些子短路徑。為了解決這個(gè)問題，我們可以先在原圖上計(jì)算最短路徑，然后從圖中刪除路徑的一條邊，然后在剩余的子圖中重新計(jì)算最短路徑。對(duì)于原始最短路徑的每一條邊，刪除邊后可以找到子圖的最短路徑。這些路徑是排序后原圖的一系列次最短路徑。Bellman-Ford算法可以應(yīng)用于具有負(fù)支出Fabian的圖，只要不存在總支出為負(fù)且從源點(diǎn)s可到達(dá)的循環(huán)（如果存在這樣的循環(huán)，則不存在最短路徑，因?yàn)榭傊С隹梢酝ㄟ^循環(huán)多次而無限減少）。

圖論中常見的最短路徑算法有幾種？都是什么？

主要有三種方法。第一種是最直接的貪婪Dijkstra算法。它可以通過使用堆數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化。缺點(diǎn)是不能找到負(fù)權(quán)重的最短路徑和判斷負(fù)回路。第二種是Bellman-Ford算法。根據(jù)松弛運(yùn)算的性質(zhì)，可以判斷負(fù)回路。時(shí)間復(fù)雜度為O（nm），三是SPFA算法。把它當(dāng)作一個(gè)算法是不太好的。其實(shí)質(zhì)應(yīng)該是上述Bellman-Ford算法具有較低的隊(duì)列優(yōu)化時(shí)間復(fù)雜度，O（KE）和K值約為2