title: Number of shortest paths exponential to the number of nodes (Dijkstra)
body: <p>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:</p>
  
  <p>A->B->C (each edge with weight 1)
  A->C (edge with weight 2)</p>
  
  <p>C->A'->B' (weight=1 for all edges)
  C->B' (weight = 2)</p>
  
  <p>B'->A''->B'' (weight=1 for all edges)
  B'->B'' (weight = 2)</p>
  
  <p>And so on...</p>
  
  <p>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.</p>
  
  <p>Thanks in advance!</p>