You can use Floyd-Warshall algorithm here.
The Floyd-Warshall algorithm finds shortest path between all pairs of vertices.
The algorithm is then very simple, go over all pairs
(u,v), and find the pair that minimized
dist(u,v)+dist(v,u), since this pair indicates on a cycle from
u with weight
dist(u,v)+dist(v,u). If the graph also allows self-loops (an edge
(u,u)) , you will also need to check them alone, because those cycles (and only them) were not checked by the algorithm.
run Floyd Warshall on the graph
min <- infinity
vertex <- None
for each pair of vertices u,v
if (dist(u,v) + dist(v,u) < min):
min <- dist(u,v) + dist(v,u)
pair <- (u,v)
return path(u,v) + path(v,u)
path(u,v) + path(v,u) is actually the path found from u to v and then from v to u, which is a cycle.
The algorithm run time is
O(n^3), since floyd-warshall is the bottle neck, since the loop takes
I think correctness in here is trivial, but let me know if you disagree with me and I'll try to explain it better.