1

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.

Matthias Kricke
  • 4,931
  • 4
  • 29
  • 43
ECE
  • 404
  • 5
  • 13
  • 6
    Remove e={v1,v2) and find the shortest path from v1 to v2? – n. m. could be an AI Feb 07 '13 at 17:24
  • 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
  • 1
    @n.m. Brilliant! Why did you not add this as an answer? – Sergey Kalinichenko Feb 07 '13 at 17:26
  • @dasblinkenlight Agreed, now my solution seems awkwardly complicated -.- – phant0m Feb 07 '13 at 17:28
  • @phant0m Why, I think your solution is pretty clean, too. – Sergey Kalinichenko Feb 07 '13 at 17:31
  • 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

1 Answers1

1

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.

phant0m
  • 16,595
  • 5
  • 50
  • 82