目标函数为∑和max的双目标最短路问题:算法和复杂性

摘要

本文研究了一个双目标最短路问题。在该问题中,一个目标函数是∑形式,另一个目标函数是max形式。首先给出了一个时间复杂性为O(m2logn)的算法产生代表有效解集合。然后研究了∑和max的组合目标函数最短路问题,对动态问题和静态问题,分别给出了一个时间复杂性都为O(m2logn)的算法。最后在字典序最优解的意义下,本文给出了两个时间复杂性都为O(mlogn)的算法。