Question: 1. Use Dijkstra's algorithm to find the shortest path from sto every other vertex in the graph shown in Figure.

2. Perhaps you recall from Example that the Restaurant Quatre-Etoile ´ offers prix fixe meals and that one of the available dishes is Foie Gras Falafel with Fig Fondue. The local geese have heard about this abomination (it is made from marinated goose liver!!), and in solidarity a coalition of ducks has joined them to protest the restaurant! However, they are not very fast walkers (they can't fly while holding signs). Can you help them by finding the shortest route from the pond to the restaurant? A map of the area is shown in Figure.

Now you should come together as a large group. Select four people to go to the front of the room (bonus if there are four whose first names begin with A, B, C, and D) and two to write on the board. A, B, C, and D should stand in a row at the front, left to right. One of the board writers should record this ordering (ABCD). Now, two of the A, B, C, D people who are next to each other should switch, and a board writer should record the new ordering. Your communal goal is to see if you can reach every possible ordering, with no repeats, by just switching two next-to-each-other people. again and again. (Such a switch is called an adjacent transposition.) Go for it-and record the orders as you go! After ten minutes or so of this fun, whether or not you have achieved your goal, break into groups to work on the following problems.

Example: The Restaurant Quatre-Etoile offers prix fixe meals only. (That ´ means you pay a fixed amount and get a k-course meal, where k usually varies between three and five. And it's pronounced "pree fix.") Their menu allows a choice of appetizers, a choice of main dishes, and a choice of desserts.