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

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

给定一个无向图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.