A few colleagues decided to carpool on the way to work. The following map displays the routes between their homes:
Starting from house A, determine the shortest path that visits every house exactly once.
A courier business has to make multiple pick-ups from several stores. The following map displays the routes between the stores:
Stores A and E need immediate pick up. Starting from store A, determine the shortest path to take if visiting every store only once.
A canned goods company has to make drops at every store in an area. The following map displays the routes between the stores:
Starting from store B, determine the shortest path to take if calling into every store only once.
The delivery man has to drop a newspaper at every house in a certain area. The following graph shows the map of that area:
The delivery man wants to be time efficient. If he enters the area at house B and leaves at house G, find the shortest path for him to travel passing by each house only once.
The firefighting department received an emergency call about a house fire across town. The following graph shows the local town map:
If the firefighting department is located at vertex L, and the house is at vertex A, find the shortest route between L and A.
The following map shows all possible routes in Mohamad's town. Mohamad travels from his home to his friend's house on a daily basis.
If Mohamad's house is vertex C, and his friend's house is vertex I, determine the shortest path between the two places.
The grocery store has to make a delivery across town. The store is known for its fast delivery. The following graph represents a map of the town:
If the store is at vertex A, and the delivery has to be made to vertex H, find the shortest path between both vertices
A group is organizing a tour in the park that ends with a picnic. The following graph displays the map of the park:
Since the tour is for the elderly, the group wants the distance from the start of the park (at vertex A), to the picnic area (at vertex J) to be as short as possible. Find the shortest route between these two vertices.
The police department receives a call about a robbery in progress at a grocery store. The following graph shows the map of the town:
If the grocery store is at vertex I, and the nearest police car is located at vertex D, determine the shortest route for the police to follow.
A mailman was allocated an area to deliver the mail to. The following table represents the routes and times between the houses:
Construct a graph based on the table.
Find the quickest route for the mailman to take, starting at house D with first delivery to house E, and passing by each house only once.
| Starting House | Ending House | Time |
|---|---|---|
| A | B | 11 |
| A | F | 9 |
| A | G | 3 |
| B | F | 5 |
| B | C | 10 |
| C | E | 8 |
| C | G | 6 |
| D | E | 5 |
| D | G | 5 |
| E | G | 7 |
For each of the following graphs, we want to find the paths of lowest weight between the vertex A and each of the other vertices:
Using Dijkstra's algorithm to find the order and label list for each vertex.
For each vertex, find the least weight between itself and vertex A.
For each of the following graphs, use Dijkstra's algorithm to find the paths of lowest weight between vertex A and each of the other vertices:
