How to find every negative cycle in a graph A graph with n vertices, no matter directed or not, may have maximally 2^n-n-1 negative cycles
(Think about combination of 2 to n elements and you'll figure out why 2^n-n-1. A graph that has no graph loops or multiple edges is my only concern)
and I want to find ALL of them if any, not just one of them. There are only answers to the latter question throughout the whole internet. To find a cycle means we get a list of vertices which form this cycle.
I also want to find the one negative cycle which is the smallest in one lap of traverse.
One solution, which is slow and not elegant, is to run Floyd-Warshall algorithm on the graph, and find those vertices, e.g. i, so that d[i][i]&lt;0 (According to some researches collected in Wikipedia, this means vertex i is part of a negative cycle) and then check all 2^n-n-1 (if there are n of those i's) cycles to see if they are negative.
First of all, there can be exponentially many negative cycles, as @Steven already mentioned.  Take $K_n$ with only negative edges.  Enumerating all of them will be bound to take exponentially long time.
You also say that you want to find the most negative cycle in the graph (which should be simple if you enumerate them all), however, in case you want a special algorithm for this problem, note that this problem is NP-complete; the reduction from Hamiltonian is straight forward.
Since you ask for any algorithm, just run, for every subset of vertices, a DP algorithm to find the Minimum Hamiltonian Cycle for that induced subgraph.  (Since you don't want to revisit an edge, you can probably find a way to add $\min_{e \in E(G)} w(e)$ to every edge, thereby avoiding all the negativity.)
(P.s., OP stated in a comment that cycles on the same vertex set are considered equivalent.)