图论最短路径分析及应用.doc

最短路径问题分析及应用 专 业： 信息与计算科学 班 级： 同组成员： 2012年06月23日北京摘要： 主要介绍最短路的两种算法，迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。以及这两种算法在实际问题中的应用和比较。关键词：图论，最短路径，迪杰斯特拉(Dijkstra)，弗罗伊德(Floyd)最短路问题及其应用1 引言图论是应用数学的一个分支，它的概念和结果来源非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、博弈问题、棋盘上马的行走路线问题等 这些古老的难题，当时吸引了很多学者的注意在这些问