[科普中國]-最短路徑算法

概述

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

（1）確定起點(diǎn)的最短路徑問題- 即已知起始結(jié)點(diǎn)，求最短路徑的問題。適合使用Dijkstra算法。

（2）確定終點(diǎn)的最短路徑問題- 與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。

（3）確定起點(diǎn)終點(diǎn)的最短路徑問題- 即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。

（4）全局最短路徑問題- 求圖中所有的最短路徑。適合使用Floyd-Warshall算法1。

算法Dijkstra算法求單源、無負(fù)權(quán)的最短路。時(shí)效性較好，時(shí)間復(fù)雜度為O（V*V+E）。源點(diǎn)可達(dá)的話，O（V*lgV+E*lgV）=>O（E*lgV）。
當(dāng)是稀疏圖的情況時(shí)，此時(shí)E=V*V/lgV，所以算法的時(shí)間復(fù)雜度可為O（V^2）。若是斐波那契堆作優(yōu)先隊(duì)列的話，算法時(shí)間復(fù)雜度，則為O（V*lgV + E）。

Floyd求多源、無負(fù)權(quán)邊的最短路。用矩陣記錄圖。時(shí)效性較差，時(shí)間復(fù)雜度O(V^3)。
Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題。

Floyd-Warshall算法的時(shí)間復(fù)雜度為O(N^3)，空間復(fù)雜度為O(N^2)。

Floyd-Warshall的原理是動(dòng)態(tài)規(guī)劃：
設(shè)Di,j,k為從i到j(luò)的只以(1..k)集合中的節(jié)點(diǎn)為中間節(jié)點(diǎn)的最短路徑的長度。
若最短路徑經(jīng)過點(diǎn)k，則Di,j,k = Di,k,k-1 + Dk,j,k-1；
若最短路徑不經(jīng)過點(diǎn)k，則Di,j,k = Di,j,k-1。
因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。

在實(shí)際算法中，為了節(jié)約空間，可以直接在原來空間上進(jìn)行迭代，這樣空間可降至二維。
Floyd-Warshall算法的描述如下：
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
if (Di,k + Dk,j Di,j ← Di,k + Dk,j;
其中Di,j表示由點(diǎn)i到點(diǎn)j的代價(jià)，當(dāng)Di,j為 ∞ 表示兩點(diǎn)之間沒有任何連接2。

Bellman-Ford求單源最短路，可以判斷有無負(fù)權(quán)回路（若有，則不存在最短路），
時(shí)效性較好，時(shí)間復(fù)雜度O（VE）。

Bellman-Ford算法是求解單源最短路徑問題的一種算法。

單源點(diǎn)的最短路徑問題是指：
給定一個(gè)加權(quán)有向圖G和源點(diǎn)s，對于圖G中的任意一點(diǎn)v，求從s到v的最短路徑。

與Dijkstra算法不同的是，在Bellman-Ford算法中，邊的權(quán)值可以為負(fù)數(shù)。

設(shè)想從我們可以從圖中找到一個(gè)環(huán)路（即從v出發(fā)，經(jīng)過若干個(gè)點(diǎn)之后又回到v）且這個(gè)環(huán)路中所有邊的權(quán)值之和為負(fù)。那么通過這個(gè)環(huán)路，環(huán)路中任意兩點(diǎn)的最短路徑就可以無窮小下去。如果不處理這個(gè)負(fù)環(huán)路，程序就會(huì)永遠(yuǎn)運(yùn)行下去。 而Bellman-Ford算法具有分辨這種負(fù)環(huán)路的能力。

SPFA是Bellman-Ford的隊(duì)列優(yōu)化，時(shí)效性相對好，時(shí)間復(fù)雜度O（kE）。（k