[comp.theory] help needed: fast way of checking the the equation

liu@cornelius.ucsd.edu (Hai-Ning Liu) (03/26/91)

I wish there was a comp.theory.help. 
Anyway, here is a problem.(This is not a final exam problem.)

Problem:
Given K pairs of vertices $  ( s_k , t_k ) , 1 \leq k \leq K $ 
in an undirected graph G ( V , E ), where E = { 1 , 2 , ..., M }
and $  c $ is a known nonnegative vector.

Is there a quick way to check whether the following condition
is satisfied?

For all $  \pi = ( \pi_1 , \pi_2 , ... , \pi_M ) \geq 0 ,$

\[  \sum_{k=1}^{K} d_k \leq \pi \cdot c , \]

where $ d_k $  being the length of shortest path,
with respect to assigning $  \pi_j , $ 
to edge $  j , 1 \leq j \leq M $ 
between $  s_k $ and $  t_k $