最短路问题及相关算法介绍吕长虹华东师范大学数学系Email:1 Av Question one ：v 每天开车去上班，应该走那条使得达到公司的费用最低、时间最少呢，如何选择最优的路径呢？2 Av Question two ：v 在城市规划自己电网架设中，怎么设计才能使其耗费的资金最少？3 Av 其实都涉及到一个相同的问题：最短路问题！4 Av 最短路问路径不仅仅是一般地理意义上的距离最短，还可以延伸到其他度量，如时间、费用、线路容量等，相应的最短路问题就转化诶最快路径问题、最低费用问题。v 最短路径问题也是资源分配，线路设计及分析等优化问题的基础。5 A 图论中的最短路问题(shortest route problem)是组合数学和图论中核心问题之一，是许多更深层次算法的基础。6 Av 图的定义：v 图是一种由“顶点”组成的抽象网络，网络中的各顶点可以通过“边”实现彼此的连接，表示两顶点有关联。图一般用G 来表示，其顶点集为V ，边集为E ，简述为G=(V,E) 。右图就是图论中一个节点的图结构，一共有10 个顶点，15 条边。Petersen 图7 Av 最短路问题就是在指定的网络
