一、負(fù)權(quán)形成環(huán)路的圖為什么不能用弗洛伊德算法求任意兩點(diǎn)之間的最短路徑

負(fù)權(quán)形成環(huán)路的圖,任意兩點(diǎn)間可能沒(méi)有最短路徑。例如負(fù)權(quán)環(huán)C，點(diǎn)A,B是C上的點(diǎn)，A可以在C中轉(zhuǎn)上任意圈后再沿C到B，這條路徑權(quán)值可以任意小。而Floyd算法可以給出網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的最短路徑。

Floyd算法的基本思想

從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑不外乎2種可能：

所以，我們假設(shè)dist(AB)為節(jié)點(diǎn)A到節(jié)點(diǎn)B的最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)K，我們檢查dist(AK) + dist(KB) < dist(AB)是否成立，如果成立，證明從A到K再到B的路徑比A直接到B的路徑短，我們便設(shè)置 dist(AB) = dist(AK) + dist(KB)，這樣一來(lái)，當(dāng)我們遍歷完所有節(jié)點(diǎn)K，dist(AB)中記錄的便是A到B的最短路徑的距離。

Floyd算法與Dijkstra算法的不同

Floyd算法是求任意兩點(diǎn)之間的距離，是多源最短路，而Dijkstra(迪杰斯特拉)算法是求一個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短路徑，是單源最短路。

Floyd算法屬于動(dòng)態(tài)規(guī)劃，我們?cè)趯?xiě)核心代碼時(shí)候就是相當(dāng)于推dp狀態(tài)方程，Dijkstra(迪杰斯特拉)算法屬于貪心算法。

Dijkstra(迪杰斯特拉)算法時(shí)間復(fù)雜度一般是o(n2),Floyd算法時(shí)間復(fù)雜度是o(n3),Dijkstra(迪杰斯特拉)算法比Floyd算法塊。

Floyd算法可以算帶負(fù)權(quán)的，而Dijkstra(迪杰斯特拉)算法是不可以算帶負(fù)權(quán)的。并且Floyd算法不能算負(fù)權(quán)回路。

延伸閱讀：

二、最短路徑問(wèn)題（SPP）

最短路徑問(wèn)題（Shortestpath problem）是圖論研究中的一個(gè)經(jīng)典算法問(wèn)題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。

最短路徑問(wèn)題根據(jù)初始條件的不同，可分為五種情況：

1）最短路徑問(wèn)題：旨在尋找圖中兩點(diǎn)之間的最短路徑；

2）確定起點(diǎn)的最短路徑問(wèn)題：即已知起點(diǎn)，求最短路徑的問(wèn)題；

3）確定終點(diǎn)的最短路徑問(wèn)題：與確定起點(diǎn)的問(wèn)題相反，該問(wèn)題是已知終點(diǎn)，求最短路徑的問(wèn)題。在無(wú)向圖中該問(wèn)題與確定起點(diǎn)的問(wèn)題完全等同，在有向圖中該問(wèn)題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問(wèn)題；

4）確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題，即已知起點(diǎn)和終點(diǎn)，求兩點(diǎn)之間的最短路徑；

5）：全局最短路徑問(wèn)題：求圖中任意兩點(diǎn)間的最短路徑。也可以合并為一種情況——全局最短路徑問(wèn)題，只要求出全局最短路徑，那其余四種情況也已經(jīng)包含在內(nèi)了。

而計(jì)算最短路徑的常用算法有迪杰斯特拉算法、貝爾曼-福特算法、弗洛伊德算法等，下面小競(jìng)將為大家一一介紹其基本概念、優(yōu)缺點(diǎn)、適用情況和案例分析。

迪杰斯特拉（Dijkstra）算法：用于解決從起點(diǎn)到其他各結(jié)點(diǎn)的最短路徑，解決的是有向圖中最短路徑問(wèn)題。其主要特點(diǎn)是以初始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止，但也有圖中不能存在負(fù)權(quán)值的邊的限制。

貝爾曼-福特(Bellman–Ford)算法：用于解決從起點(diǎn)到其他各節(jié)點(diǎn)的最短距離。與迪杰斯特拉算法不同的是，貝爾曼-福特算法可支持存在負(fù)權(quán)重的情況，即打破了圖中不能存在負(fù)權(quán)值的邊的限制，其邊的權(quán)值可以為負(fù)數(shù)、實(shí)現(xiàn)簡(jiǎn)單，但也存在時(shí)間復(fù)雜度過(guò)高的缺點(diǎn)。可對(duì)原始算法進(jìn)行若干優(yōu)化，提高效率。貝爾曼-福特算法可用于解決以下問(wèn)題：

1）從A出發(fā)是否存在到達(dá)各個(gè)節(jié)點(diǎn)的路徑(有計(jì)算出值當(dāng)然就可以到達(dá))；

2）從A出發(fā)到達(dá)各個(gè)節(jié)點(diǎn)最短路徑(時(shí)間最少、或者路徑最少等)；

3）圖中是否存在負(fù)環(huán)路（權(quán)重之和為負(fù)數(shù)）。