最短路径文献翻译终极版(共19页).doc

精选优质文档-倾情为你奉上单位代码 01 学号 分 类 号 O24 密 级 文献翻译最短通路问题 院(系)名称信息工程学院 专业名称信息与计算科学 学生姓名许秀成 指导教师孙贵玲2013年 3 月 10 日专心-专注-专业8. 6 最短通路问题8.6.1引言 许多问题可以用边上赋权的图来建模。考虑一下航线系统如何建模。如果用顶点表示城市，用边表示航线。给边赋上城市之间的距离，就可以为涉及距离的问题建模；给边赋上飞行时间，就可以为涉及飞行时间的问题建模；给边赋上票价，就可以为涉及票价的问题建模。图861显示了给一个图的边赋权的三种不同方式，分别表示距离，飞行时间和票价。2534里程旧金山洛杉矶