Finding shortest cycles containing two nodes

2
votes

Let G=(E,V) be a directed graph with non-negative edge costs. Let s be a vertex. I need to find an algorithm that finds for each vertex v, the shortest cycle that contains both s and v. The cycle may contain the same edge several times.

The obious solution is to run Dijkstra from s in order to find the shortest path from s to each v. Then, from each v to run Dijkstra again in order to find the shortst path from v to s. The shortest cycle is the combination of the two.

This works but will take O(|V||E| + |V|^2*log|V|). Is there a better solution?

1
algorithmgraph-theorydijkstra
I think this question is better suitable for a Math forum. - Michel Keijzers
Yes, there's a solution that runs Dijkstra twice. - David Eisenstat
math.stackexchange.com - Michel Keijzers
@MichelKeijzers This is very much a Computer Science question, it might be better suited for Computer Science, but these questions fit on Stack Overflow as well. It doesn't sound like a Mathematics question, but I could very well be wrong. - Bernhard Barker

1 Answers

4
votes

For directed graph, you can use Floyd-Warshall Algorithm to find shortest path between all two pairs.

Or a more efficient solution could be to run Dijsktra on the reversed graph (G'=(V,E') such that for each (v,u) in E, (u,v) is in E'), and concat the two solution (one in reverse of course). This is basically running Dijkstra twice.