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
Network Engineering Stack Exchange is a question and answer site for network engineers. It only takes a minute to sign up.Sign up to join this community
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.)