First, solve the single-destination shortest path problem for target vertex t. The interview question specifies an undirected graph, so single-destination t is equivalent to single-source t. If it were a directed graph, reverse all edges and then apply Dijkstra's algorithm with target vertex t as the "source". Now walk along the shortest path from the source vertex s to the target vertex t. At each vertex v along this shortest path, consider taking a single step to the side by exploring all vertices x adjacent to v where x is not the next vertex on the shortest path. Calculate distance(s, v) + distance(v, x) + distance(x, t). Record the minimum value found. It will be the second shortest path. distance(s, v) can be summed incrementally as you walk away from s. distance(v, x) is the length of a single edge. distance(x, t) was calculated and stored in the first step for all vertices x. The rationale of this algorithm is to make only one "misstep" along the path from s to t. After making the misstep, follow the new optimum path to t. Choose the misstep that minimizes the cost of the error. The misstep could even be a single step backwards along the shortest path.