3
$\begingroup$

Let $G=(V,E)$ be a weighted directed graph with edge-weights given by linear functions $f_i(x) = ax-b$, $0 < a < 1$, $b > 0$. For a given starting parameter $x_0$, a path from $v_i$ to $v_j$ across edges $e_0, e_1, e_2, ... e_n$ is given a cost of $x_0 - f_n(f_{n-1}(...(f_1(f_0(x_0)))...))$. The problem is to find the center of the graph - the node with the minimal cost to reach any other node.

As an example of this problem, consider a vehicle traversing roads between cities. The vehicle has very poor gas mileage per weight of fuel, so that $x$ represents fuel remaining, and $f_i(x)$ represents the remaining fuel in the tank after traversing the road with $x$ amount of fuel in the tank to start with. The goal is to determine which starting city would allow the smallest possible amount of fuel in the tank to start with.

The only way I can think of is exhaustively testing each node to find the smallest $x_0$ which would reach all other nodes on the graph, and then select the node with the smallest $x_0$. Is there a faster way?

$\endgroup$
1
$\begingroup$

Sounds like you have an all-pairs shortest path problem. I guess there isn't a non-exhaustive way to solve it. The complexity is around $O(|V|^3)$.

$\endgroup$
  • $\begingroup$ This sounds pretty likely, thanks! $\endgroup$ – Foo Barrigno Jul 3 '13 at 16:34

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.