New answers tagged

3

The problem of finding the shortest simple cycle through two vertices in a weighted undirected graph can be solved in the same time as Dijkstra's algorithm for a single shortest path, by applying Suurballe's algorithm for finding disjoint $s$–$t$ shortest paths in a directed graph. It doesn't quite work to turn your given undirected graph directed by ...


Top 50 recent answers are included