3.1 基于Dijkstra算法的路徑分析

Dijkstra（迪杰斯特拉）算法是典型的最短路徑路由算法，也是一種單源路徑算法，用于計(jì)算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。該算法的主要特點(diǎn)是以起始點(diǎn)為中心向外層擴(kuò)展，知道擴(kuò)展到終點(diǎn)為止，Dijkstra算法對處理非負(fù)權(quán)邊的最短路徑問題是比較高效的。Dijkstra算法方法簡明，能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所有效率低，同時運(yùn)算時占用空間大。

3.1.1 應(yīng)用示例：極地探險

3.1.2 基于Dijkstra的最短路徑規(guī)劃

Dijkstra算法時很有代表性的最短路徑算法，其思想是，設(shè)置頂點(diǎn)集合S并不斷地進(jìn)行貪心選擇來擴(kuò)充這個集合。一個頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該點(diǎn)的最短路徑長度已知。

初始時，S中僅含有源。設(shè)U是G的某一個頂點(diǎn)，把從源到U且中間只經(jīng)過S中頂點(diǎn)的路稱為從從源到U的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個頂點(diǎn)所對應(yīng)的最短特殊路徑長度。Diskstra算法每次從V-S中取出具有最短特殊路長度的頂點(diǎn)U，將U添加到S中，同時對數(shù)組dist進(jìn)行必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其他頂點(diǎn)之間的最短路徑長度。