How Do You Design an Algorithm for This Graph

Question

Introduction

I'm not really understanding my algorithms class. One of our HW assignments is to design an efficient algorithm for this graph

Questions

1. Give an efficient algorithm to find the fastest route for Alice to leave home, reach some gas station, then get to work.

2. On her way home, Alice wants to visit both a grocery store and a hardware store (in some order). Give an efficient algorithm to find the fastest route for Alice to leave work, visit both stores, and get home.

Thoughts

I was thinking something along the lines of A* search and make Gas Stations have a 0 heuristic, or something like create a list of the shortest paths and choose the shortest path with a gas station?

Honestly, I don't know how to implement this. How do I go about reasoning about this?

For example, how would I implement my second solution?

Answer 1

Both questions can be solved in time $O(m + n \log n)$, where $n$ and $m$ are the the number of vertices and edges of the input graph graph $G$.

For question $1$: Create a directed graph $G'$ consisting of two copies of $G$ (you can think of $G$ as directed by replacing each undirected edge $\{u,v\}$ with the two directed edges $(u,v)$ and $(v,u)$).

For each vertex $v$ that represents a gas station in $G$, let $v_1$ and $v_2$ be the vertices corresponding to $v$ in the first and second copy of $G$ in $G'$, respectively, and add the directed edge $(v_1, v_2)$ to $G'$. The weight of $(v_1, v_2)$ is $0$. Finally, find the shortest path $P$ from home (in the first copy of $G$) to work (in the second copy of $G$). The length of $P$ is exactly of the shortest route from home to work that passes through a(t least one) gas station.

Question $2$ can be solved similarly. First, guess the order in which the stores are visited (there are only $2$ possible choices). Then, create a graph $G'$ with 3 copies of $G$. Intuitively, going from the first copy to the second copy means visiting the first store, and going from the second copy to third copy means visiting the second store.