C語(yǔ)言對(duì)于用bfs求最短路徑的同時(shí)，如何記錄路徑？例如，如果地圖是二維數(shù)組地圖[n][M]，并且記錄了從起點(diǎn)到每個(gè)點(diǎn)的最短路徑（由BFS獲得），則可以從終點(diǎn)向后推，即如果終點(diǎn)為x1，Y1，dist[x

C語(yǔ)言對(duì)于用bfs求最短路徑的同時(shí)，如何記錄路徑？

例如，如果地圖是二維數(shù)組地圖[n][M]，并且記錄了從起點(diǎn)到每個(gè)點(diǎn)的最短路徑（由BFS獲得），則可以從終點(diǎn)向后推，即如果終點(diǎn)為x1，Y1，dist[x1][Y1]=D，（Xi，Yi）是與（x1，Y1）相連的點(diǎn)，如果dist[Xi][Yi]=D-1，然后它可以從（Xi，Yi）到（x1，Y1），然后繼續(xù)尋找，直到找到起點(diǎn)。在Dijkstra算法的基礎(chǔ)上做一些修改，可以擴(kuò)展Dijkstra算法的功能。

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

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

首先，BFS會(huì)在每個(gè)步驟中將所有可能的后續(xù)步驟存儲(chǔ)到陣列中。然后，數(shù)組指針向后移動(dòng)一位，即BFS同時(shí)遍歷所有可能的遍歷方法。也就是說(shuō)，同時(shí)，行走方法陣列中的未定位置所采取的步數(shù)相同（或者只有1個(gè)差）。這樣，當(dāng)?shù)竭_(dá)終點(diǎn)時(shí)，算法必須有最少的步數(shù)。DFS就是走一條路到盡頭，然后換另一條路。你可以想象，當(dāng)一條非常迂回的道路恰好到達(dá)終點(diǎn)時(shí)，DFS將被判斷為計(jì)算出來(lái)的，當(dāng)然這不是最短的