分享到微信
信息系统项目管理师综合知识真题考点：图与网络分析-最短路径问题
温馨提示：该考点请多结合试题进行理解。
最短路径问题常用Dijkstra标号法进行求解，该方法可用于求解指定两点vs,vt间的最短路，或从指定点vs到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。
算法的基本思路：若序列{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是物流集散地，其他点均为不同的二级转运站，弧上的数字代表两点间的距离(单位公里)，则V1到二级运转站（）最远，其最短路径为（）公里。
（1）A．V6
B．V7
C．V8
D．V9
（2）A．17
B．14
C．13
D．11查看答案
参考答案：B、C
信管网订阅号
信管网视频号
信管网抖音号
温馨提示：因考试政策、内容不断变化与调整，信管网网站提供的以上信息仅供参考，如有异议，请以权威部门公布的内容为准！
信管网致力于为广大信管从业人员、爱好者、大学生提供专业、高质量的课程和服务，解决其考试证书、技能提升和就业的需求。
信管网软考课程由信管网依托10年专业软考教研倾力打造，教材和资料参编作者和资深讲师坐镇，通过深研历年考试出题规律与考试大纲，深挖核心知识与高频考点，为学员考试保驾护航。面授、直播＆录播，多种班型灵活学习，满足不同学员考证需求，降低课程学习难度，使学习效果事半功倍。
相关内容
| 发表评论 查看完整评论 | |
考试新手指南
学习计划攻略
精华备考资料
案例论文干货
章节模拟试题
免费试听课程
考试信息推送