# Is the number of shortest paths between every two vertices at most 4*n^3?

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?

• How does this question relate to cs.stackexchange.com/questions/109488/… – David Richerby May 17 at 21:42
• @Zuran, do you mean "with non-negative weights"? "with negative weights" sounds rather strange, although whether the weights are negative or not does not affect the answer. – Apass.Jack May 17 at 22:26
• Can you credit the source where you originally encountered this problem? – D.W. May 18 at 18:45

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.