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

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

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

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 strictly 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( n4) time algorithm to solve the strictly third shortest path problem in the undirected graph with positive weight.