1

I am stuck on a two part practice problem regarding the subjects mentioned in the title.

The first part of the question asks: By considering the complete graph with n verticies, show that the maximum number of simple paths between two verticies is O((n-1)!). (I am assuming I am supposed to show this somehow with a formal definition)

The second portion of the questions asks: Give an example where Dijkstra's algorithm gives the wrong answer in the presence of a negative edge but no negative cost cycles.

Thanks for any help!

Nick
  • 95
  • 3
  • 15
  • There are two questions here, and on SO we expect one question per thread. The 2nd question is answered in: [why Dijkstra's algo does not work for negative weight edges](http://stackoverflow.com/q/13159337/572670). – amit Apr 16 '14 at 15:52
  • First question is a simple induction, the second is finding a small example of such a graph (of which, if you can't come up with one yourself, there are numerous to be found online). – G. Bach Apr 16 '14 at 15:54
  • Regarding the first part, there are (n-1)! simple maximal paths (of length `n`), but there are more paths if you consider 1->2->3 as different than 1->2. – amit Apr 16 '14 at 15:55
  • @G.Bach How would I go about proving the induction though? The only time I have have used induction is when I have two equations set equal to one another. In this case, we only have one two work with. – Nick Apr 16 '14 at 16:08
  • You do induction on the number of vertices of the graph. Start proving it for two vertices, then assume that the bound holds for some n>=2 and prove it for n+1. – G. Bach Apr 16 '14 at 16:11
  • @amit With the addition of "Between two vertices" the upper bound is still correct I believe. The number of simple paths is 1! + 2! + ... + (n-2)! <= (n-2)*(n-2)! <= (n-1)! – Niklas B. Apr 16 '14 at 16:20
  • @NiklasB. If you don't restrict yourself to simple paths, then any cycle will give an infinite number of paths, no? – G. Bach Apr 16 '14 at 16:24
  • @G.Bach Of course I meant simple paths. I edited the comment – Niklas B. Apr 16 '14 at 16:25
  • Thank you everyone for the responses! – Nick Apr 16 '14 at 16:27
  • @NiklasB. Well that a subset of all simple paths is smaller than the set of all simple paths is not much additional information. – G. Bach Apr 16 '14 at 16:38
  • @G.Bach I kind of got stuck here, am I doing this right so far? O(n-1)! basis: O(2-1)!=1 This holds true assume: O(k-1)! Prove: O((k+1)-1)! =O(k)! – Nick Apr 16 '14 at 16:41
  • @G.Bach There are omega((n-1)!) simple paths in the graph if I'm not mistaken. In fact there should even be omega((n-1)!) simple paths starting at a given vertex, but O((n-1)!) if you fix the end node as well. – Niklas B. Apr 16 '14 at 16:42
  • @Nick Yeah that sounds about right; I just realized that maybe a combinatorial proof might be easier. – G. Bach Apr 16 '14 at 16:46
  • @NiklasB: Actually there are exactly (n-1)! simple paths starting at a fixed vertex, and (n-2)! simple paths between two fixed vertices (if we fix which vertex is start and which is target, otherwise there are 2*(n-2)!). – G. Bach Apr 16 '14 at 16:46
  • @G.Bach But that isn't the end of the proof. Doesn't the induction proof have to prove that it can go back to the original (k-1)! after the induction step? So from (k)! I need to somehow prove that I can get back to (k-1)! – Nick Apr 16 '14 at 16:47
  • @G.Bach That's only the paths of length (n-1). There are many more though – Niklas B. Apr 16 '14 at 16:48
  • @NiklasB. You're right, I forgot about those. There may be o((n-1)!) simple paths between two fixed vertices (you could probably use Stirling's approximation for that), but there are definitely Omega((n-1)!) simple paths starting at a given vertex. – G. Bach Apr 16 '14 at 16:51
  • @Nick Maybe induction is not the easiest approach here after all; try thinking about how you can build paths from s to t. – G. Bach Apr 16 '14 at 16:58
  • @G.Bach The only proofs we know so far is induction, and contradiction. I'm sure I will eventually figure it out. Thanks for the good start – Nick Apr 16 '14 at 17:07

0 Answers0