Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!pacbell.com!ucsd!sdcc6!cornelius!liu
From: liu@cornelius.ucsd.edu (Hai-Ning Liu)
Newsgroups: comp.theory
Subject: help needed: fast way of checking the the equation
Message-ID: <17777@sdcc6.ucsd.edu>
Date: 25 Mar 91 22:22:48 GMT
Sender: news@sdcc6.ucsd.edu
Distribution: na
Lines: 19

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 $