Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
In every weighted graph with $n$-vertices
with negative weights,
with $n > 10$,
a weight can't appear $n$-times in graph,
there are between every two vertices at most $4n^3$ shortest paths.
I'm trying to prove whether the statement above is true or false, however I am clueless. So far I failed to find a graph where there would be more than $4n^3$ shortest paths so I'm guessing it's true?
Consider the following graph, where we have $3\times 4+1=13$ nodes, $a1, b1, c1, a2, b2, c2, a3, b3, c3, a4, b4, c4, a5$ and $4\times4=16$ edges $a1b1, a1c1, b1a2, c1a2, \cdots, a4b4, a4c4, b4a5, c4a5$ with weights $1,1,1,1,\cdots, 4,4,4,4$ respectively.
Every path from $a1$ to $a5$ is a shortest path between them since all of them have the same weight (length). There are $2^4=16$ of them.
Consider extending this graph to a much larger graph, following the same pattern. For example, suppose we will have $100\times3+1=301$ nodes and $100\times4+1=400$ edges. Now compute how many shortest paths there are between $a1$ and $a301$.
Exercise 1. Construct a graph with the same constraint such that there are more than $4n^3$ paths of the same weight between every two vertices.
