Let's use graph searching to optimize our holiday season!
Write a function named holidayShopping that helps a person find the best route for doing their holiday shopping.
You will search for a minimum-weight path in a graph of stores to purchase a set of products on your shopping list.
Your function accepts four parameters:
graph: A reference to a BasicGraph, a weighted undirected graph where each vertex represents a store selling various products, and each edge represents the road to travel between those stores.
start: A string representing a starting vertex name.
products: A reference to a set of integers representing a list of products you need to buy.
For simplicity we represent products by integers.
For example, the set {1, 4, 8} means you need to buy products #1, #4, and #8.
stores: A reference to a map from strings to sets of integers, where the keys are stores (vertex names) and the values are sets of integers representing the products for sale at that store.
For example, if store A sells products #4 and #7, the pair of ("A", {4, 7}) will be present in the map.
Your job is to find the minimum-weight path in the graph, starting at the given vertex, that visits enough stores to purchase all of the products on the person's shopping list.
You do not necessarily need to visit every vertex, just enough of them to buy all of the items.
The key is that you must find the minimum-weight such path.
You should return a real number representing the total weight of the best such path once you find it.
Whenever a path travels to a given vertex, you must purchase any items at that store that are on your shopping list.
Consider the following example graph.
We indicate the products for sale at each store in {...} in each vertex; this corresponds to what would be found in the stores map for that vertex name.
Suppose we want to buy products numbered #1 through #9 inclusive, starting from vertex A.
Here are some of the paths that would allow us to purchase all products:
- You could travel {A, B, E, G, F, C, D, H}, buying products #4,7 at A; #2,5 at B; #1,8 at E; #9 at G; #6 at F; nothing at C or D; and #3 at H.
This path has a total weight of 31.
- You could travel {A, F, H, I, D}, which has a total weight of 19 and is therefore better than the previous one.
- You could travel {A, B, G, F, H, I}, buying products #4,7 at A; #2,5 at B; #9 at G; #6 at F; #3 at H; and #1,8 at I.
This path has a total weight of 12 and turns out to be the best possible such path in the graph.
So if your function were called on the graph above, you should return 12 as the best path's weight.
If no path exists to purchase all products in the given graph, return INT_MAX.
(You may assume that all acyclic paths in the graph have total weights less than INT_MAX.)
Assumptions: You may assume that the graph's state is valid.
You may assume that it is an undirected graph; in other words, that if there is an edge from any v1 to v2, there will also be an edge from v2 to v1.
You may assume that all edges have positive weights.
You may assume that the graph contains no self-edges (e.g. from v1 to v1).
You may assume that there is at most one edge from any vertex v1 to any other vertex v2.
You may assume that every vertex in the graph is represented as a key in the stores map.
You may assume that the products set is initially non-empty.
You may not assume that the graph is connected, nor make any other assumptions about the number or names of its vertexes or edges.
Efficiency:
To be certain that you have found the best path, you must exhaustively try every possible path.
This can be a slow process.
Your code is not required to have any particular Big-Oh, but you must (a) refrain from exploring identical paths more than once; (b) refrain from exploring paths farther than necessary (past the point where all items have been purchased, etc.); and (c) avoid grossly inefficient data structures to represent your computations along the way.
Constraints: Do not modify the contents of the graph such as by adding or removing vertexes or edges from the graph.
You may define helper functions if desired.
You may construct auxiliary collections as needed to solve this problem.
