Second Shortest Simple Path (Shortest Path (Directed Graphs))

Description

Given a weighted digraph $G=(V,E)$, find the second shortest path between two given vertices $s$ and $t$.

Related Problems

Generalizations: st-Shortest Path

Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, 1-sensitive (3/2)-approximate ss-shortest paths, 2-sensitive (7/5)-approximate st-shortest paths, 1-sensitive decremental st-shortest paths, 2-sensitive decremental st-shortest paths, Replacement Paths Problem

Parameters

No parameters found.

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
Minimum Triangle	if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$ then: from-time: $T(O(n), O(nW))$ for $n$ node graph with integer weights in $(-W, W)$	2018	https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/3186893, Theorem 5.5	link
Distance Product	if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$ then: from-time: $O(n^{2} T(O(n^{1/3}), O(nW)) \log W)$ for two $n\times n$ matrices with weights in $(-W, W)$	2018	https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/3186893, Theorem 5.5	link
Directed, Weighted APSP	if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$ then: from-time: $O(n^{2} T(O(n^{1/3}), O(n^{2}W)) \log Wn)$ for graphs with weights in $(-W, W)$	2018	https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/3186893, Theorem 5.5	link