一個極簡的Dijkstra算法示例

Dijkstra算法是一種用于計算一個起點(diǎn)到其他所有點(diǎn)的最短路徑的算法。它是貪心算法的一種，基于貪心策略，用來找單源最短路徑問題。該算法常用于路由算法和作為其他圖算法的一個子模塊。 Dijkstra算法的時間復(fù)雜度為O(E + VlogV)。

下面是一個使用 Dijkstra 算法求最短路徑的示例：

假設(shè)有一張圖，有節(jié)點(diǎn) A, B, C, D, E，邊的權(quán)重如下：

A -> B : 3

A -> C : 5

B -> C : 1

B -> D : 7

C -> D : 2

C -> E : 4

D -> E : 1

要求從節(jié)點(diǎn) A 到節(jié)點(diǎn) E 的最短路徑。

首先，我們將所有節(jié)點(diǎn)初始化為未確定狀態(tài)。

A 的距離為 0，其余節(jié)點(diǎn)距離為正無窮。

接著，我們選擇距離最小的節(jié)點(diǎn)進(jìn)行更新。

選擇 A，將其狀態(tài)設(shè)為已確定。

更新 B, C 的距離: B(3), C(5)

接下來選擇下一個距離最小的節(jié)點(diǎn)進(jìn)行更新。

選擇 B，將其狀態(tài)設(shè)為已確定。

更新 C, D 的距離: C(4), D(9)

以此類推，直到所有節(jié)點(diǎn)都被確定，最終得到最短路徑 A->B->C->D->E，長度為7

這只是一個簡單的示例，在實(shí)際應(yīng)用中，Dijkstra算法通常需要使用優(yōu)先隊列來維護(hù)未確定節(jié)點(diǎn)的距離，以提高效率。