Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs

Shisheng Li

Given a directed graph with positive edge weights and two vertices s,t, a next-to-shortest s-t path is a shortest simple s-t path among those whose length is strictly larger than t…