For a given graph G=(V,E) and an edge e∈E, design an O(n+m)-time algorithm to find, if it exists, the shortest cycle that contains e

Question

Trying to understand graphs and having a really hard time with this. I know how to find the shortest path, but not sure how you can find the shortest cycle and still make it in O(n+m) time?

not really looking for free code. just maybe a general idea of how to think about it. Maybe psuedo code could best achieve this. And yes, by 'm+n' I mean 'V + E' — ka123444, Feb 14 '17 at 16:39
Define "cycle". One could argue that (a, b) in E is already a cycle of length 2. — Niklas B., Feb 14 '17 at 16:54
"cycle": a path V1, V2, ..., VK in which V1 = VK, K > 2, and V1, V2, ..., Vk-1 are distinct. the graph is undirected. thanks! — ka123444, Feb 14 '17 at 17:10
Maybe try with a DFS, even if it will not return the shortest path, then the BFS and then Floyd-Warshall — mychemicalro, Feb 14 '17 at 17:29

score 0 · Accepted Answer · edited May 23 '17 at 12:09

the shortest cycle that contains e

BFS is perfect for that. A cycle will be the goal. Time complexity is the same.

You want something like this(Edited from Wikipedia):

Cycle-With-Breadth-First-Search(Graph g, Edge e):

    remove e from E
    root is b where e = (a,b)
    create empty set S
    create empty queue Q      

    root.parent = a
    Q.enqueueEdges(root)                      

    while Q is not empty:

        if current = a
            return current

        current = Q.dequeue()
        for each node n that is adjacent to current:
            if n is not in S:
                add n to S
                n.parent = current
                Q.enqueue(n)

For more info about cycles and BFS read this link https://stackoverflow.com/a/4464388/6782134

thank you so much! this was really helpful, along with the resources! — ka123444, Feb 15 '17 at 01:21

For a given graph G=(V,E) and an edge e∈E, design an O(n+m)-time algorithm to find, if it exists, the shortest cycle that contains e

1 Answers1