k最短可靠路径及其优化问题

摘要

k最短路径在边失效模型中,存在一个等长路径的选择问题,基于可靠性的选择是有效的解决方案.这里提出了一种k最短路径限制下的可靠性模型来度量k最短路径,进一步把等长路径的选择问题转化为一个可靠性优化问题,即选择使得可靠性最大的k最短路径.最终通过设计近似算法有效地解决了优化问题,实例证明了该算法的有效性.