Directed graphs: Use any max-flow algorithm together with the max-flow min-cut theorem. There are any number of algorithms for max-flow in an arbitrary directed graph. This is bog-standard stuff that should be covered in any algorithms textbook. See also minimum cut.
Undirected graphs: Use a min-cut algorithm for undirected graphs, e.g., Karger's algorithm or this lecture. I don't know what you mean by "it is not guaranteed to provide a solution"; the probability that it fails to find a solution is exponentially small, e.g., you can make this probability smaller than the chance that a cosmic ray hits your computer, makes it compute the wrong answer, and then you get struck by lightning and die anyway. Tough luck about that lightning, by the way.
Next time do more research before asking.