1
$\begingroup$

Introduction

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

enter image description here

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?

$\endgroup$
  • 2
    $\begingroup$ What exactly is your question? Do you want to find the shortest path from Home to Work which passes through at least one each of Gas Station, Grocery Store and Hardware Store? $\endgroup$ – CodeChef Apr 9 at 16:34
  • 1
    $\begingroup$ It is impossible to advise you without knowing what is the problem you are trying to solve. $\endgroup$ – Steven Apr 9 at 16:36
  • 2
    $\begingroup$ I'm not sure what is an efficient algorithm for a graph. For me, an algorithm solves a problem. What is the problem that the algorithm is supposed to solve? $\endgroup$ – Yuval Filmus Apr 9 at 17:34
  • $\begingroup$ Just updated the question. Dumb of me -_- Thank you @CodeChef et. all $\endgroup$ – Michaelslec Apr 9 at 17:44
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think OP has a weighted graph, going by what I assume are edge weights in the figure. So it wouldn't be linear time, and the weight of the edges between the copies of the graph would have to be 0. $\endgroup$ – CodeChef Apr 10 at 4:00
  • 1
    $\begingroup$ Thank you! I edited my answer. $\endgroup$ – Steven Apr 10 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.