1. Introduction
We consider the algorithmic problem of finding a cycle of minimum weight in weighted directed and undirected graphs. Surprisingly, although the problem is very fundamental, the state of the art for it dates back to a seminal paper by Itai and Rodeh [10] from the 1970s, that deals only with the unweighted variant of the problem. Itai and Rodeh presented an -time algorithm for an n-node unweighted undirected graph and an -time algorithm for an n-node unweighted directed graph. (Here is the exponent of square matrix multiplication over a ring; [4].) In the same paper, Itai and Rodeh posed the question whether similar results exist for weighted graphs. In this paper we provide a positive answer to this longstanding open problem by presenting -time algorithms for directed graphs with integral edge weights in (and no negative cycles) and for undirected graphs with integral edge weights in .