无向图中严格第三短路问题的多项式时间算法

• 作者: 曾庆红
• 来源期刊: 云南民族大学学报（自然科学版）
• 学科: 数学
• 关键词: 最短路 次短路 严格第三短路 最小费用流
• 年，卷（期）: 2014,（1）
• 所属期刊栏目: 数学与应用数学
• 页码范围: 58-61
• 页数: 4页
• 分类号: O157.5
• 字数: 4601字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-8513.2014.01.013

摘要

给定一个无向图G=(V,E;w;s,t),其中s,t是2个固定顶点,w:E→R+是边的长度函数.最短路是指所有路中长度最小者,次短路是指长度比最短路严格大的所有路中的最小者,严格第三短路是指长度比次短路严格大的所有路中的最小者.对正权重无向图中严格第三短路问题给出一个O(n4)多项式时间算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曾庆红	保山学院数学学院	18	30	3.0	5.0