Dijkstra（Dijkstra）算法是一種典型的最短路徑路由算法，用于計(jì)算從一個(gè)節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是從頭到尾展開。Dijkstra一般有兩種表達(dá)方式，一種是永久和臨時(shí)標(biāo)記，另一

Dijkstra（Dijkstra）算法是一種典型的最短路徑路由算法，用于計(jì)算從一個(gè)節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是從頭到尾展開。Dijkstra一般有兩種表達(dá)方式，一種是永久和臨時(shí)標(biāo)記，另一種是開放的，閉表模式采用開閉表模式，采用貪心法的算法策略，一般過程如下：

1。聲明兩個(gè)集合，open和close，open用于存儲(chǔ)尚未遍歷的節(jié)點(diǎn)，close用于存儲(chǔ)已遍歷的節(jié)點(diǎn)

2。在初始階段，將初始節(jié)點(diǎn)置于關(guān)閉狀態(tài)，將所有其他節(jié)點(diǎn)置于打開狀態(tài)

3。以初始節(jié)點(diǎn)為中心逐層遍歷，得到離指定節(jié)點(diǎn)最近的子節(jié)點(diǎn)，將其放入閉合點(diǎn)，計(jì)算路徑，直到閉合點(diǎn)包含所有子節(jié)點(diǎn)。代碼示例如下：使用node對(duì)象封裝節(jié)點(diǎn)信息，包括名稱和子節(jié)點(diǎn)[Java]視圖純拷貝公共類節(jié)點(diǎn){private string name private首先，在不考慮時(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行代碼。