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.)

| improve this answer | |

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