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 仓库
