Q:

Finding shortest cycles containing two nodes

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?

A:

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.

