分享到微信
信息系統(tǒng)項目管理師綜合知識真題考點：圖與網(wǎng)絡分析-最短路徑問題
溫馨提示：該考點請多結合試題進行理解。
最短路徑問題常用Dijkstra標號法進行求解，該方法可用于求解指定兩點vs,vt間的最短路，或從指定點vs到其余各點的最短路，目前被認為是求無負權網(wǎng)絡最短路問題的最好方法。
算法的基本思路：若序列{vs，v1，...vn-1,vn}是從vs到vn的最短路，則序列{vs，v1，...vn-1}必為從vs到vn-1的最短路。
算法描述：
1、初始時，P只包含起點v1;T包含除v1外的其他頂點，且T中頂點的距離li為起點v1到該頂點的距離。
2、從T中選出距離起點v1最短的頂點k，并將頂點k加入到P中;同時，從T中移除頂點k。
3、 更新T中各個頂點到起點v1的距離。之所以更新T中各頂點的距離，是由于上一步中確定了k是求出最短路徑的頂點，從而可以利用k作為跳板來更新其它頂點的距離。例如，T中有一點s和k相鄰，s到起點v1的距離可能大于k到v1的距離+k到s的距離。
4、重復步驟2和3，直到遍歷完所有頂點。
考點相關真題
-
圖中V1是物流集散地，其他點均為不同的二級轉運站，弧上的數(shù)字代表兩點間的距離(單位公里)，則V1到二級運轉站（）最遠，其最短路徑為（）公里。
（1）A．V6
B．V7
C．V8
D．V9
（2）A．17
B．14
C．13
D．11查看答案
參考答案：B、C
信管網(wǎng)訂閱號
信管網(wǎng)視頻號
信管網(wǎng)抖音號
溫馨提示：因考試政策、內(nèi)容不斷變化與調(diào)整，信管網(wǎng)網(wǎng)站提供的以上信息僅供參考，如有異議，請以權威部門公布的內(nèi)容為準！
信管網(wǎng)致力于為廣大信管從業(yè)人員、愛好者、大學生提供專業(yè)、高質量的課程和服務，解決其考試證書、技能提升和就業(yè)的需求。
信管網(wǎng)軟考課程由信管網(wǎng)依托10年專業(yè)軟考教研傾力打造，教材和資料參編作者和資深講師坐鎮(zhèn)，通過深研歷年考試出題規(guī)律與考試大綱，深挖核心知識與高頻考點，為學員考試保駕護航。面授、直播＆錄播，多種班型靈活學習，滿足不同學員考證需求，降低課程學習難度，使學習效果事半功倍。
相關內(nèi)容
| 發(fā)表評論 查看完整評論 | |
考試新手指南
學習計劃攻略
精華備考資料
案例論文干貨
章節(jié)模擬試題
免費試聽課程
考試信息推送