0

I came across this question and I have no clue how to prove. Any help would be appreciated.

Q) Prove that a shortest path across a graph is loop free

  • 1
    Different protocols use different methods to make sure that paths are loop-free. You need to be more specific. – Ron Maupin Nov 5 '15 at 21:32
  • 3
    Loops mean there will be more hops. QED (A-B-C-B-D is more hops than A-B-D) – Ricky Beam Nov 5 '15 at 21:49
  • 2
    This looks suspiciously like a homework question. – Ron Trunk Nov 6 '15 at 12:14
4

By contradiction: Suppose p is the shortest path across the graph and p has a loop. Remove the loop. The new loop-less path across the graph is shorter than p. We have achieved a contradiction, so our initial supposition must be false.

(This applies only if "shortest" means "smallest sum of edge weights" and there are no negative edge weights.)

Not the answer you're looking for? Browse other questions tagged or ask your own question.