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).
Correction: The following algorithm finds a collection of one or more disjoint trails of minimum total weight.
We reduce the problem of finding a collection of trails of minimum weight to the minimum cost circulation program (with positive and negative costs), which in turn can be solved using linear programming. Consider a directed graph $G=(V,E)$. Assign each edge in $G$ capacity one. Then every “closed directed trail” or a collection of vertex-disjoint “closed directed trails” corresponds to a flow circulation in $G$ (which satisfies capacity constraints). Conversely, suppose that we are given an integral circulation (the amount of flow on every edge is either 0 or 1). Consider the set of edges $E'\subset E$ on which the amount of flow is 1. Then the graph $(V,E')$ is a union of directed Eulerian graph (for every vertex, the number of incoming edges is equal the number of outgoing edges; the graph is not necessarily connected). Therefore, there is a collection of vertex disjoint “closed directed trail” (a collection of vertex-disjoint Eulerian cycles in $(V,E')$) that is formed exactly by edges from $E'$.
Now we can find the minimum cost circulation efficiently (see Wikipedia) e.g. using Linear Programming (note that the circulation polytope is integral and thus linear programming gives an integral solution, in which the amount of flow on every edge is either 0 or 1).