1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ How does this question relate to cs.stackexchange.com/questions/109488/… $\endgroup$ – David Richerby May 17 at 21:42
  • $\begingroup$ @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. $\endgroup$ – Apass.Jack May 17 at 22:26
  • 1
    $\begingroup$ Can you credit the source where you originally encountered this problem? $\endgroup$ – D.W. May 18 at 18:45
1
$\begingroup$

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.

Graph made by Apass.Jack using https://graphonline.ru/en/ 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.

$\endgroup$

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.