Dijkstra算法 -- 這是我職業(yè)生涯中唯一一個(gè)會(huì)寫(xiě)，卻叫不上名字的算法
Dijkstra算法是一種單源最短路徑算法，用于找出圖中從一個(gè)源點(diǎn)到其他所有點(diǎn)的最短路徑。該算法的原理是采用貪心策略，每次將距離源點(diǎn)最近的點(diǎn)加入到已確定最短路徑的集合中，并更新其它節(jié)點(diǎn)的距離。具體實(shí)現(xiàn)過(guò)程如下：
-
初始化距離數(shù)組dist[]，源點(diǎn)距離為0，其余點(diǎn)距離為無(wú)窮大。
-
將所有點(diǎn)加入到未確定最短路徑的集合中。
-
在未確定最短路徑的集合中找出距離源點(diǎn)最近的節(jié)點(diǎn)v，并將其加入到已確定最短路徑的集合中。
-
對(duì)節(jié)點(diǎn)v的所有鄰居節(jié)點(diǎn)u進(jìn)行更新，如果dist[u] > dist[v] + w(v,u)，則更新dist[u] = dist[v] + w(v,u)，其中w(v,u)是v到u的邊權(quán)值。
-
重復(fù)步驟3和4，直到所有節(jié)點(diǎn)都被加入到已確定最短路徑的集合中。
Dijkstra算法的時(shí)間復(fù)雜度為O(V^2)，其中V為節(jié)點(diǎn)數(shù)。如果使用優(yōu)先隊(duì)列來(lái)優(yōu)化實(shí)現(xiàn)，時(shí)間復(fù)雜度可以優(yōu)化到O(ElogV)，其中E為邊數(shù)。
relax -- 松弛操作
松弛操作是指在圖論中，對(duì)某個(gè)節(jié)點(diǎn)的估計(jì)值進(jìn)行更新的過(guò)程。通常用于單源最短路徑算法，例如Dijkstra算法和Bellman-Ford算法中。具體來(lái)說(shuō)，當(dāng)我們使用Dijkstra算法或Bellman-Ford算法計(jì)算從源節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑時(shí)，我們維護(hù)一個(gè)估計(jì)值列表，表示從源節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)的距離估計(jì)，隨著算法的執(zhí)行，我們逐步更新這個(gè)列表，直到找到最短路徑。
對(duì)于Dijkstra算法，我們通過(guò)選擇距離源節(jié)點(diǎn)最近的未標(biāo)記節(jié)點(diǎn)來(lái)進(jìn)行松弛操作，并更新源節(jié)點(diǎn)到該節(jié)點(diǎn)的距離估計(jì)值。以節(jié)點(diǎn)u為例，假設(shè)當(dāng)前我們已經(jīng)確定從源節(jié)點(diǎn)到節(jié)點(diǎn)u的距離估計(jì)值為d[u]，而節(jié)點(diǎn)u有一個(gè)鄰居節(jié)點(diǎn)v，且u和v之間有一條邊e(u,v)，邊e(u,v)的權(quán)重為w(u,v)，我們可以通過(guò)以下方式來(lái)更新v的距離估計(jì)值：
d[v] = min(d[v], d[u] + w(u,v))
其中，min表示取兩個(gè)值的較小值，即如果u到v的距離比當(dāng)前估計(jì)值更短，則更新d[v]為新的估計(jì)值。
對(duì)于Bellman-Ford算法，我們對(duì)所有的邊進(jìn)行松弛操作，直到不能再進(jìn)行更新為止。以邊e(u,v)為例，我們可以通過(guò)以下方式來(lái)更新v的距離估計(jì)值：
if d[u] + w(u,v) < d[v]:
? ? d[v] = d[u] + w(u,v)
其中，if語(yǔ)句的意思是，如果u到v的距離比當(dāng)前估計(jì)值更短，則更新d[v]為新的估計(jì)值。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-637662.html
需要注意的是，Bellman-Ford算法可以處理負(fù)權(quán)邊，而Dijkstra算法只適用于圖中沒(méi)有負(fù)權(quán)邊的情況。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-637662.html
到了這里，關(guān)于【圖論】單源最短路問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
