Shortest Paths in undirected cyclic graphs

Question

Can someone please explain how given an undirected graph G = (V; E); edge lengths le > 0; and edge edges in E.

We can generate the length of the shortest cycle containing edge e.

I understand how to do this in directed graphs, but im not sure how to approach the problem with an undirected graph.

Why do you have a `DAG` tag on this question, if the graph is undirected and you are looking for a cycle? If the ends of `e` are `v1` and `v2`, then the shortest cycle in undirected graph would be the trivial one `v1-v2-v1` :-) I'm sure this isn't what you're looking for, so you may want to clarify that the cycle needs to have at least three edges. — Sergey Kalinichenko, Feb 07 '13 at 17:25
@dasblinkenlight Agreed, now my solution seems awkwardly complicated -.- — phant0m, Feb 07 '13 at 17:28
possible duplicate of [Cycles in an Undirected Graph](http://stackoverflow.com/questions/526331/cycles-in-an-undirected-graph) — Mr. Alien, Feb 08 '13 at 12:08
@dasblinkenlight Well, just considering the explanations, mine needs a lot more words... without giving more understanding — phant0m, Feb 09 '13 at 10:54
@Mr.Alien It's not a duplicate. This asks for the shortest cycle containing a specific edge. The other is about cycle detection. — phant0m, Feb 10 '13 at 12:53

score 1 · Answer 1 · answered Feb 07 '13 at 17:25

Without modifying the graph: Let e be an edge (u, v). Choose one of the two nodes—I'll choose u—and run an ordinary Dijkstra/BFS starting from u with one minor modification: When making the first hop, you must not add v to the queue. Now search for v.

Shortest Paths in undirected cyclic graphs

1 Answers1