Problem Variations

Variations of the Shortest Path Problem

Problem 3:

Solve the single-pair shortest-path problem for the graph below and the pair .

Figure 7:

Answer

What method did you use to find the shortest paths? (Or did you just "come across" a shortest path by accident?) Did you find both of the shortest paths? Take a moment now to write down a method you would use to automate a search for a shortest path between any two vertices in an arbitrary graph.