Graph theory: shortest path with vector weights

Question

I have a strongly connected digraph with edges weighted with vectors, where each vector has only non-negative entries. I want to find a cycle such that the angle between the sum of the weights and a diagonal vector ([1, 1, 1, ... 1]) is minimized. Are there any algorithms out there for this sort of thing?

I'm fairly confident a Bellman-Ford type algorithm would give me a fairly good solution, but I'm not convinced that it will be the -best-...

Answer 1

Since arcs can be used multiple times, this problem can be formulated as a quadratic program. If the instance is not large, then it might be worthwhile to try one of the solvers that Wikipedia links to.

Let's take feasible solutions to be circulations x, i.e., positive linear combinations of simple cycles. Let A be the matrix representing the linear map from arcs to vectors. There's one trick, proved with a little algebra: instead of minimizing the angle of Ax relative to the all-ones vector, we minimize the length of Ax subject to the constraint that the dot product of Ax and the all-ones vector be 1.

Now we can write down the quadratic program.

minimize y1^2 + ... + yn^2 (positive semidefinite objective)
subject to
Ax - y = 0
x is a circulation

The last constraint breaks down as the linear constraints x >= 0 and, for each vertex, that the sum of x values on arcs entering the vertex equals the sum of x values on arcs leaving.

Answer 2

as far as I understand the Bellman-Ford Algo it seems, that Dijkstra Shortest Path Algo does the same. But it's way faster couse of its greedy behaviour.

Edit: Dijkstra only works with non-negative entries. But that would fit your Problem

Answer 3

Consider two cycles that share a common vertex. It's totally possible that there are positive integers p and q so that p times the vector for the first cycle added to q times the vector for the second cycle exactly equals a multiple of (1,1,...,1). Thus, unless you restrict to simple cycles, I don't think there is a fast algorithm for you that's provably optimal. Even if you restrict to simple cycles though, you could have part of a cycle equal to a vector x and the rest of the cycle equal to a vector c(1,1,...,1) - x, and you'd probably have no way to know this unless you enumerated all cycles and just check them. Thus I think brute force enumerating cycles may be the only feasible way to approach your problem if you want an optimal solution.