最短路问题(共12页).doc

网络图中最短路问题专题研究报告报告人：张鹏学号：20090828班级：035109012011年5月12日网络图中最短路问题 【问题导引】网络分析在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要作用。而最短路问题是网络分析中最基本、最关键的问题。最短路径不仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间，费用等等。这些都可以抽像为在图中找出任意两点间的一条通路，使这条通路上的权值和最小。最短路问题作为图与网络技术研究的一个经典问题，在工程规划、地理信息系统、通信和军事运筹学等领域有十分广泛的应用。举例如下： 【案例一】：如图的交通网络，图中的点表示交通节点，每条边表示两个节点间的一条通路，边上的数字表示路段的长度，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？10237411