CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithmshortest-path
ECE
ECE

Reputation: 414

Shortest Paths in undirected cyclic graphs

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.

Upvotes: 1

Views: 1968

Answers (1)

phant0m
phant0m

Reputation: 16905

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.

Upvotes: 1

Related Questions