信息系統(tǒng)項目管理師綜合知識真題考點(diǎn)：圖與網(wǎng)絡(luò)分析-最短路徑問題

溫馨提示：該考點(diǎn)請多結(jié)合試題進(jìn)行理解。

最短路徑問題常用Dijkstra標(biāo)號法進(jìn)行求解，該方法可用于求解指定兩點(diǎn)vs,vt間的最短路，或從指定點(diǎn)vs到其余各點(diǎn)的最短路，目前被認(rèn)為是求無負(fù)權(quán)網(wǎng)絡(luò)最短路問題的最好方法。

算法的基本思路：若序列{vs，v1，...vn-1,vn}是從vs到vn的最短路，則序列{vs，v1，...vn-1}必為從vs到vn-1的最短路。

算法描述：

1、初始時，P只包含起點(diǎn)v1;T包含除v1外的其他頂點(diǎn)，且T中頂點(diǎn)的距離li為起點(diǎn)v1到該頂點(diǎn)的距離。

2、從T中選出距離起點(diǎn)v1最短的頂點(diǎn)k，并將頂點(diǎn)k加入到P中;同時，從T中移除頂點(diǎn)k。

3、 更新T中各個頂點(diǎn)到起點(diǎn)v1的距離。之所以更新T中各頂點(diǎn)的距離，是由于上一步中確定了k是求出最短路徑的頂點(diǎn)，從而可以利用k作為跳板來更新其它頂點(diǎn)的距離。例如，T中有一點(diǎn)s和k相鄰，s到起點(diǎn)v1的距離可能大于k到v1的距離+k到s的距離。

4、重復(fù)步驟2和3，直到遍歷完所有頂點(diǎn)。

考點(diǎn)相關(guān)真題