Dijkstra算法:

1.本算法求解指定兩點(diǎn)間的最短路,或從指定點(diǎn)到其余各點(diǎn)的最短路。

2.本算法目前被認(rèn)為是求無(wú)負(fù)權(quán)網(wǎng)絡(luò)最短路問(wèn)題的最好方法。

3.本算法基于貪心算法。

4.基本流程:

1. 初始化所有頂點(diǎn)到源點(diǎn)的距離。

2. while 循環(huán)找到最近的頂點(diǎn) u 進(jìn)行標(biāo)記。

3. 在 while 循環(huán)中,更新頂點(diǎn) u 的所有出邊頂點(diǎn) v 到源點(diǎn)的距離。方程可得:?

4. 循環(huán)直到所有頂點(diǎn)標(biāo)記完就 break。

5. 最終 dis[i] 中存的都是源點(diǎn)到 i 點(diǎn)的最短路徑值。

Floyd算法:

算法特點(diǎn):Floyd 算法是解決任意兩點(diǎn)的最短路徑的一種算法,可以正確處理有向圖,可帶有負(fù)權(quán)(但不可存在負(fù)權(quán)回路)的最短路徑問(wèn)題.

算法思路: 對(duì)于每一對(duì)頂點(diǎn) u 和 v,看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w?再到 v?比 u->v 的路徑最短,如果是,更新他.

算法結(jié)果: edge[i][j]?為 i 到 j?的最短路徑.

算法優(yōu)點(diǎn): 代碼簡(jiǎn)單,適合求多源最短路徑.

算法缺點(diǎn):時(shí)間復(fù)雜度較高O(),不適合大量數(shù)據(jù).

注：有些地方叫 Flody，是同一種算法。

SPFA算法:

本算法用來(lái)求解單源最短路徑的算法,和 dijkstra 算法不同在于,SPFA能夠存在負(fù)權(quán)值,但不能有負(fù)環(huán).但是，關(guān)于SPFA,他死了——時(shí)間復(fù)雜度太高！具體可以去知乎參考：zhihu.com/question/292283275