第7章 图论-4(最短路问题)VIP免费

1返回结束第七章图论引言7

1图的基本概念7

2路与连通7

3图的矩阵表示7

4最短路径问题7

5图的匹配图的匹配8

1Euler8

1Euler图和图和HamiltonHamilton图图8

3生成树生成树8

4平面图平面图2返回结束7

4最短路问题一、问题的提出)(G赋权图（网络）：G=(V,E)中，给每条边a=赋予一个非负实数权wij，得到一个有向网络3返回结束7

4最短路问题路径路径长度路径长度非带权图的路径长度是指此路径上边的条数

带权图的路径长度是指路径上各边的权之和[距离矩阵]对上述网络，定义D=(dij)nn，n=|V|wij当Edij=其它[带权路径长度]对上述网络，路径v1,v2,…,vk的带权路径长度定义为1,11kiiidw4返回结束7

4最短路问题最短路问题在实际工作中应用1、通讯网络中最可靠问题2、最大容量问题3、统筹方法中求关键路线4、背包问题5、选址问题6、工件加工顺序问题7、中国邮递员问题背包问题(Knapsackproblem)是一种组合优化的NP完全问题

问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高

问题的名称来源于如何选择最合适的物品放置于给定背包中

5返回结束7

4最短路问题例一位旅客要从A城到B城1

他希望选择一条途中中转次数最少的路线；2

他希望选择一条途中所花时间最短的路线；3

他希望选择一条途中费用最小的路线；v5v4v3v2v1v01006030101020550这些问题均是带权图上的最短路径问题

边上的权表示一站2

边上的权代表距离3

边的权代表费用6返回结束7

4最短路问题Dijkstra算法Floyd算法Floyd-Warshall算法7返回结束7

4最短路问题Dijkstr