时变网络中零等待时间最短路问题的一个对偶算法

• 作 者: 朱建明 沙丹
• 机 构: 上海师范大学数理信息学院,上海对外贸易学院国际经贸学院
• 出 处: 上海师范大学学报：自然科学版
• 发表日期: 2008年1期
• 关键词: 最短路 对偶算法 时变网络 最优化 shortest path dual algorithm time - varying network optim
• 基金项目: Foundation item： Partially supported by Shanghai Municipal Education Commission with project number 5Z1206.

时变最短路问题是最短路问题的一个推广．假设图C=（V，A）是一个有向图且有唯一的源点s，图G中的每条弧（i,j）∈A都附有两个参数：弧的传送时间b（i，j，u）和弧的传送费用c（i，j，u），它们都是在弧的顶点i上的出发时间u的函数．找出从源点到其它各点的最短路，即最小费用的路，并且要求每条最短路的传送时间不能超过给定的时间限制T，假设除源点外，在其它任何顶点都不能等待，b（i，j，u）是满足u＋b（i，j，u）≥0（V（i，j）∈A，u=0，1，．．．，T）的任意整数，c（i，j，u）是任意的非负整数．