1.最短路问题的含义
• 连通图的最短路问题指求两个顶点间长度最短的路径。
对最短路径问题的描述如下:
假设有一n个节点和m条弧的连通图G(Vn,Em),并且图 中的每条弧(i,j)都有一个长度cij(或者费用cij),则 最短路径问题为:在连通图G中找到一条从节点1到节点n距 离最短(或费用最低)的路径。
习题
• 方案1:三晚都住在汽车旅馆M2中, 住宿费是每晚49.00美元。
• 方案2:前两晚都住在汽车旅馆M1 中,走访客户l至9,住宿费为每 晚40.00美元。随后,搬到汽车旅 馆M3住一晚,走访客户10至18, 住宿费是每晚45.00美元。在走访 客户l至9后,推销员回到M1,在 此过夜。随后,搬到M3,过夜并 于次日早晨离开。M1和M3相距36 英里。不管丹在这个地区的什么 地方,旅行成本都是0.30美元/ 英里。
连通图G(Vn,Em)中,从指定起始点到指定目的点之间的 最短路径。
连通图G(Vn,Em)中,从指定起始点到其余所有节点之间 的最短路径。
住宿费: 40 + 40 + 45 = 125 美元
旅行费用:211.70×0.30 = 63.51美元
总成本:
188.51美元
采用第二种方案最好
16
二. 点点间运输——最短路径求解方法 (配送货物由一个配送中心直达某客户)
• 最短路问题的含义 • 最短路问题的基本原型 • 求解最短路问题的算法
17
之后再取货。 • 7.对偏离集聚停留点路线远的单独的停留点可应用另一个送
货方案。 • 8.应当避免停留点工作时间太短的约束。
5
1.将相互接近的停留点的货物装在一辆车上运送
停留点
D 仓库