2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Because you only allow one use of each edge, your problem is equivalent with the case where the edges have positive weights : $w_{ij}-\min w_{ij}$. And if I understood correctly (which is not always the case), you problem is linear (cost function), you should be able to resort to standard minimization techniques on graph ? $\endgroup$ – Bertrand R Aug 16 '13 at 6:45
  • $\begingroup$ Bertrand R, I don't see how. If it were truly equivalent, then Djikstra's algorithm would work out. But, how would a greedy algorithm work out in this case? The problem is that the total distance for a path can now decrease as you traverse a subsequent node. Thus, once you visit the final node (in the case of my question, this is the starting node again), you're no longer guaranteed that the route you took to get there is the shortest path there. $\endgroup$ – Mike Battaglia Aug 16 '13 at 6:49
1
+50
$\begingroup$

The problem can be reduced 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” 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 directed Eulerian graph (for every vertex, the number of incoming edges is equal the number of outgoing edges). Therefore, there is a “closed directed trail” (an Eulerian cycle in $(V,E')$) that consists of edges from $E'$: each edge $e\in E'$ appears on the trail exactly once, each edge on the trail is in $E'$.

We have a one-to-one correspondence between “closed directed trails” and integral circulations in $G$. Accordingly, the minimum cost trail corresponds to the minimum cost (integral) circulation. 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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.