怎么求最短路徑？最短路徑問題是圖論中的一個(gè)經(jīng)典算法問題，其目的是尋找圖中兩個(gè)節(jié)點(diǎn)之間的最短路徑。算法的具體形式包括：1。確定起始點(diǎn)的最短路徑問題，即起始節(jié)點(diǎn)已知時(shí)尋找最短路徑的問題。2. 確定終點(diǎn)的最

怎么求最短路徑？

最短路徑問題是圖論中的一個(gè)經(jīng)典算法問題，其目的是尋找圖中兩個(gè)節(jié)點(diǎn)之間的最短路徑。

算法的具體形式包括：1。確定起始點(diǎn)的最短路徑問題，即起始節(jié)點(diǎn)已知時(shí)尋找最短路徑的問題。

2. 確定終點(diǎn)的最短路徑問題與確定起點(diǎn)的問題相反，問題是在終點(diǎn)已知的情況下尋找最短路徑。在無(wú)向圖中，問題等價(jià)于起點(diǎn)的確定問題。在有向圖中，問題等價(jià)于通過反轉(zhuǎn)所有路徑的方向來(lái)確定起點(diǎn)的問題。

3. 確定起點(diǎn)和終點(diǎn)之間最短路徑的問題是在已知起點(diǎn)和終點(diǎn)的情況下，求兩個(gè)節(jié)點(diǎn)之間的最短路徑。

4. 全局最短路徑問題-尋找圖中的所有最短路徑。

涉及的算法包括Dijkstra算法、a*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法等

可根據(jù)不同的需要選擇不同的算法。

過n個(gè)點(diǎn)的最短路徑怎么求？

利用遺傳算法和模擬退火算法，可以得到次優(yōu)解。或者一次從一個(gè)點(diǎn)遍歷所有點(diǎn)，找到距離最短的點(diǎn)，連接，然后以下面的點(diǎn)為起點(diǎn)，找到一個(gè)沒有連接的點(diǎn)，是距離最短的點(diǎn)，連接，依次進(jìn)行，知道找到最后一個(gè)點(diǎn)。這是數(shù)學(xué)上證明的最短的一個(gè)

我們可以在Dijkstra算法的基礎(chǔ)上做一些修改來(lái)擴(kuò)展它的函數(shù)。

例如，有時(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)多次而無(wú)限減少）。

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

首先，在不考慮時(shí)間復(fù)雜度的情況下，解決了圖論中的最短路徑問題。這個(gè)基本問題也可以推廣到許多其他的理論或?qū)嵺`問題。

最短路徑問題有一個(gè)理想的時(shí)間復(fù)雜度（<=O（n^2）），但是如果我們找到圖中任意兩點(diǎn)之間的距離，特別是當(dāng)圖是稠密的時(shí)候，F(xiàn)loyd的O（n^3）就不比其他問題小。

Floyd的另一個(gè)優(yōu)勢(shì)是易于編寫。完成了插點(diǎn)、三循環(huán)、一判斷、五要素的簡(jiǎn)單構(gòu)思。Dijkstra在堆優(yōu)化和SPFA之后需要大約50行代碼。