CODEWITHSUNDEEP
graphgraph-algorithmdijkstra
Proghero
Proghero

Reputation: 669

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

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!

Upvotes: 0

Views: 1826

Answers (1)

Origin
Origin

Reputation: 2017

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.

Upvotes: 1

Related Questions