Number of shortest paths exponential to the number of nodes (Dijkstra)

Question

I was asked to figure out a kind of graph whose total number of shortest paths (using Dijkstra's algorithm) is exponential to the number of nodes. I came up with a graph like that:

A->B->C (each edge with weight 1) A->C (edge with weight 2)

C->A'->B' (weight=1 for all edges) C->B' (weight = 2)

B'->A''->B'' (weight=1 for all edges) B'->B'' (weight = 2)

And so on...

This way, the total number of shortest paths found by Dijkstra's algorithm for this graph would be Ω(2^(n/2)). I'm now trying to figure out, if it can be generalized in something like Ω(2^(n/k)), where k = number of shortest paths per node. I also still don't know, how I can properly prove the correctness of the solution. Any advice or hint very appreciated! I also would appreciate if you would point out any existing flaw in my solution.

Thanks in advance!

Just to be clear: you want to design a graph which has an exponential number of (shortest) paths between 2 nodes. Are these 2 nodes fixed or should there be an exponential number of paths between any 2 nodes? — Origin
Hi @Origin, thanks for your response! Actually, I want a graph which has an overall exponential number of shortest paths relatively to the number of nodes (i.e. some nodes may have fewer paths leading to them than other nodes have, but what counts is the total number of shortest paths that the whole graph has). Maybe there's a more general form of the solution I gave. It does not have to be only between 2 nodes. The total number of shortest paths possibly could be expressed like Ω(c^(n/k)). And that's what I'm looking for. I hope it helped clarify things a little bit! — Proghero

Origin Origin · Accepted Answer · 2012-10-27T23:35:25

Your solution is a good starting point. The number of solution can be doubled that way for every few nodes you add. However, I do not immediately see how every node would have about the same amount of shortest paths. This could lead to an average that is lower, which would nullify your proposal.

To solve that problem, you can make 2 slight adjustments to your graph: make it cyclical and add some more links.

make it cyclical: You should connect your starting node with your last node. This would make every node in the graph equal so all of them have the same number of shortest paths.

add some more links: In your example you give node A a link to node B and a link to node C. You should also give node B a link to node C (already ok) and a link to node A'. This equal to eachother.

To prove the correctness, you can now calculate the number of distinct path for 1 node to all other nodes and that's a valid result for all nodes in the graph (which is why they should be equal). To prove the exponentiality, you could look at what happens if you add more nodes to your graph and how that impacts the number of solutions.

Number of shortest paths exponential to the number of nodes (Dijkstra)

1 Answers