金陵科技学院南04到1302教室的最短路规划问题.pptx

《金陵科技学院南04到1302教室的最短路规划问题.pptx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、南04到1305教室的最短路规划问题小组成员：王琴琴刘子吟洪欣王慧婷数据来源：解决思路：建立最短路问题数学模型的目标为从起点南区四号宿舍楼出发到终点北区1305教室，确定最佳的路线以实现路程最短。线路规划图：南区食堂大活图书馆北区食堂北区03教学楼31305教室333m289m830m600320m473m496m542m333.6m316m400m南区04Dijkstra算法:对每个节点，用两种标号：T和P，表示从始点到该节点的距离，P是最短距离，T是目前路径的距离。通过不断改进T值，当其最小时，将其改为P标号。开始时，令始点有P=0，P标号，其它

2、节点T=M（无穷大）。第一步：假定vi是新产生的P标号点，考查以vi为开始点的所有弧段vivj。如果vj是P标号点，则对vj点不再进行标号；如果vj是T标号点，则计算第二步：产生新的P标号点，在现有所有的T标号中将值最小的T标号改为P标号。重复上述步骤,直到没有点可标号。步骤：最终结果：V1V2V3V5V7V4V8333289830600320473496542333.6316400V6P=0T=M=333=P(V1,333)T=M=622=P(V2,622)T=M=920=P(V3，920)(V1,600)T=M=600=PT=M=1073=P(V

3、3,1073）(V3,1096)T=M=1096=P(V7,1362)T=M=1362=P(V4,1452）(V5，1462)(V6，1406.6)V1-南区04V2-南区食堂V3-大活V4-教学楼3V5-图书馆V6-北区食堂V7-北区03V8-教室1305总结：所以线路V1→V3→V7→V8路径最短为1362给大家最好的建议是：南区04→大活→北区03→教室1305这条线路最为节省力气