I'm using the following definition of a "closed directed trail": a closed directed trail is a directed cycle in a digraph where all edges are distinct. Note that vertices may be repeated, so long as each edge appears no more than once.
If I have a weighted digraph with negative weights allowed, I want to be able to find the "shortest" (aka "most negative") closed directed trail in the graph.
If it makes it easier, I'd be happy to solve the problem just for a given vertex that the trail must start and end on.
The problem of finding the shortest cycle for digraphs with negative weights allowed is typically ill-defined, since for any cycle with a negative distance, you can trivially come up with an even more negative one just by going through the cycle again. However, for closed directed trails, this no longer holds, since if you go through a trail twice in a row, it's no longer a trail (since edges are no longer distinct).
I've been looking at ways to modify Djikstra's algorithm or the Bellman-Ford algorithm to solve this problem, but I'm still not really sure I've found the best way to do it. Has this problem (or something sufficiently similar) been worked out before? Is there some known algorithm to handle this situation?
One can obviously just find "all cycles" in the graph and then work out the distance of each one, but that's a naive approach that isn't very optimized, and I'm hoping for something that can scale reasonably well.
I'd also be happy to know algorithms that can handle a subset of this situation, for example those which can detect the length of the shortest simple cycle in a graph with negative weights (simple meaning no vertices OR edges repeated).