28.2.2. Properties of Shortest Paths

Try these first

1. 1.

   What defines a shortest path in a graph?

   Hint

   Think about the weights of the edges.

2. 2.

   Can a shortest path have repeating vertices?

   Hint

   Consider the effect of looping back.

3. 3.

   What is the maximum number of edges in a shortest path across n vertices?

   • n
   • n-1
   • n+1

   Hint

   Consider how many unique vertices could be traversed without revisiting.

4. 4.

   True or False: A shortest path can revisit vertices if there's a negative edge.

   • True
   • False

   Hint

   Think about the impact of a loop on the path total.

5. 5.

   Design a graph that contains a negative cycle. Explain how the Bellman-Ford algorithm might respond.

   Hint

   Make sure to set the edge weights purposely so that the total is negative when summed.

6. 6.

   Given a set of edges, apply the Bellman-Ford algorithm to find the shortest path from the source vertex to all others and illustrate your steps.

   Hint

   Count iterations carefully! Remember, you will need n-1 runs through the edge list.