运筹学第六章 图与网络模型 第3节 最短路问题
- 格式:ppt
- 大小:3.37 MB
- 文档页数:36
实验六:图与网络分析-最短路问题
一、实验目的:掌握不同问题的输入方法,求解网络模型,观察求解步骤,显示并读出结果。
二、内容和要求:用WinQSB软件求解最短路问题,并对结果进行简单分析。
例:求下图的最短路。
三、操作步骤:
1.“开始”菜单→“winQSB”→“Network Modeling”(网络模型)。
2.建立新问题:File→New Problem,出现下面界面。
选择Shortest Path Problem、Minimization、输入问题标题、节点的个数,然后单击“OK”。
3.修改节点名称:菜单“Edit”→“Node Names”,编辑完点“OK”,如下图。
4.按下图输入图的权矩阵,本例是无向图,每一条边必须输入两次。
5.菜单“Solve and Analyze”→“Solve the Problem”,出现以下对话框,
6.然后选择起点v1和终点v10,点“Solve”按键,出现下图:
从图中可以看到v1到v10的最短路径为v1→v3→v7→v10,总长为6,另外从v1到其他各点的最短距离也都计算了出来。
7.实例求解:有九个城市v1,v2…,v9,其公路网如下图,弧旁数字是该段公路的长度,有一批货物从v1运到v9,试用Dijkstra方法求出走哪条路最短?
自己先用标号法求出最短路,然后用winWSB软件进行验证。
8.思考题:教育部门打算在某新建城区建一所学校,让附近七个居民区的学生就近入学。
七个居民区之间的道路如下图所示,学校应建在哪个居民区,才能使大学都方便?(图中距离单位:百米)。