顶点赋权区间图最重权路径问题研究

周星利; 李鹏

doi:10.14045/j.cnki.15-1220.2024.06.004

内蒙古民族大学学报（自然科学版） ›› 2024, Vol. 39 ›› Issue (6) : 24 -31. DOI: 10.14045/j.cnki.15-1220.2024.06.004

顶点赋权区间图最重权路径问题研究

周星利, 李鹏

作者信息 +

Author information +

文章历史 +

摘要

区间图是数轴上一组区间构成的相交图，由点、边构成，拥有清晰简洁的优美结构。区间表示与区间图一一对应，体现为一组区间的相交情况。在区间图G的对应区间表示I上，借助正规路径（NP），设计了一个多项式算法来解决顶点赋权区间图的最重权路径问题，该算法包含固定右端点的最重权路径的求解程序，证得在O（n³）运行时间内可解，其中n为输入区间图的顶点数，即可在多项式时间O（n³）内搜索并查找出一条给定赋权区间图上各顶点权值之和最大的路径。