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

Polynomial time algorithm of the strictly third shortest path problem in the undirected graph

作　　者：曾庆红 

机构地区：[1]保山学院数学学院,云南保山678000

出　　处：《云南民族大学学报（自然科学版）》2014年第1期58-61,共4页Journal of Yunnan Minzu University:Natural Sciences Edition

基　　金：云南省应用基础研究计划项目(2013FD054);保山学院校级科研教研项目(BBZ010)

摘　　要：给定一个无向图G=(V,E;w;s,t),其中s,t是2个固定顶点,w:E→R+是边的长度函数.最短路是指所有路中长度最小者,次短路是指长度比最短路严格大的所有路中的最小者,严格第三短路是指长度比次短路严格大的所有路中的最小者.对正权重无向图中严格第三短路问题给出一个O(n4)多项式时间算法.Given an undirected graph G = （ V, E ; w ; s, t）, where s and t are two fixed vertices, and w ： E→R^＋ is the length function. The shortest path is the path with the minimum length of all paths. A next - to - shortest path is a shorter path amongst all the paths having the length strictly greater than the length of the shortest path. A strict- ly third shortest path is the shortest path amongst all paths having the length strictly greater than the length of a next - to - shortest path. The paper proposes an O （ n^4 ） time algorithm to solve the strictly third shortest path problem in the undirected graph with positive weight.

关 键 词：最短路 次短路 严格第三短路 最小费用流 

分 类 号：O157.5[理学—数学]