尋找最短路徑時(shí)，是BFS和Dijkstra的算法有什么區(qū)別？在Dijkstra算法的基礎(chǔ)上作一些改動(dòng)，可以擴(kuò)展其功能。例如，有時(shí)希望在求得最短路徑的基礎(chǔ)上再列出一些次短的路徑。為此，可先在原圖上計(jì)算出

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

在Dijkstra算法的基礎(chǔ)上作一些改動(dòng)，可以擴(kuò)展其功能。

例如，有時(shí)希望在求得最短路徑的基礎(chǔ)上再列出一些次短的路徑。為此，可先在原圖上計(jì)算出最短路徑，然后從圖中刪去該路徑中的某一條邊，在余下的子圖中重新計(jì)算最短路徑。對(duì)于原最短路徑中的每一條邊，均可求得一條刪去該邊后子圖的最短路徑，這些路徑經(jīng)排序后即為原圖的一系列次短路徑。Bellman-Ford算法可用于具有負(fù)花費(fèi)邊的圖，只要圖中不存在總花費(fèi)為負(fù)值且從源點(diǎn) s 可達(dá)的環(huán)路(如果有這樣的環(huán)路，則最短路徑不存在，因?yàn)檠丨h(huán)路循環(huán)多次即可無限制的降低總花費(fèi))。