Question

Design a linear-time algorithm which, given an undirected graph G and a particular edge e in it, determines whether G has a cycle containing e. Your algorithm should also return the length (number of edges) of the shortest cycle containing e, if one exists. Just give the algorithm, no proofs are necessary. Hint: you can use BFS to solve this.

Answer 1

SOLUTION:

FROM THE GIVEN PROBLEM

This can be reduced to Shortest Path Problem:

Find the shortest path from v to u, then the shortest cycle that contains (u,v), is v->...->u->v, where v->...->u is the shortest path from v to u as found by the shortest path algorithm.

It can be solved efficiently using Dijkstra's Algorithm, since there are no negative weights in the graph.

Correctness Proof:

Assume there is a cheaper cycle v1->v2->...vi->u->v->v_i+1->...->vn->v1. Let's say it weights x < d(v,u) + w(u,v)
Since it's a cycle, we can look at it as v->v_i+1->....->vn->v1->...->vi->u->v.
The weight of the cycle didn't change, and is still x. This means x=w(v,v_i+1) + ... + w(vn,v1) + ... + w(v_i-1,vi) + w(vi,u) + w(u,v)
But this gives us w(v,v_i+1) + ... + w(vn,v1) + ... + w(v_i-1,vi) + w(vi,u) + w(u,v) - w(u,v) < d(v,u), and we have found a shorter path from v to u, than d(v,u), which is contradicting correctness of Dijkstra's Algorithm.