patternMinor
Graph Algorithm (Modification on Dijkstra?) : Tech Interview
Viewed 0 times
dijkstragraphtechalgorithminterviewmodification
Problem
Problem: Suppose we had a directed graph $G(V,E)$ with strictly positive edge weights, a nonempty set $A$ (special vertices) such that $A \subseteq V$, a positive integer $C$, and a starting vertex $S \in V$. Find the shortest path starting at $S$ and containing at least $C$ vertices in $A$ (cycles are OK). If no path exists, output -INF or +INF. Polynomial time algorithms only (in $V$, $E$, and $C$).
My attempt: If there are at least $C$ vertices in $A$ that I want to find, then maybe I could replicate the graph $C$ times, where each replicated graph is like a layer. So when running Dijkstra, if I step into a special vertex, that vertex connects me to its counterpart in the next layer. If there are 10 vertices in the graph and I want to find when I step into the special vertices 3 times, then there will be 30 total vertices because each layer contains the identical looking 10 vertices.
I have issues translating this idea to any sort of (pseudo) code. Perhaps my idea isn't even valid; in that case, any help would be appreciated in proposals of a different solution.
My attempt: If there are at least $C$ vertices in $A$ that I want to find, then maybe I could replicate the graph $C$ times, where each replicated graph is like a layer. So when running Dijkstra, if I step into a special vertex, that vertex connects me to its counterpart in the next layer. If there are 10 vertices in the graph and I want to find when I step into the special vertices 3 times, then there will be 30 total vertices because each layer contains the identical looking 10 vertices.
I have issues translating this idea to any sort of (pseudo) code. Perhaps my idea isn't even valid; in that case, any help would be appreciated in proposals of a different solution.
Solution
The Hamitonian path problem is reducible to your problem. Given a directed graph $G(V,E)$, set $C=|V|$ (number of nodes), $A = V$, and weight of each edge is equal to $1$. Thus, this instance of the problem requires to find a shortest path containing all vertices. Since it asks to find the shortest path, cycles are not allowed, and since it asks to include all vertices, the path visits all vertices once. This is a Hamiltonian path. So, your problem is NP-complete meaning it is unlikely to find a polynomial time algorithm. In this case you should try approximation algorithms or Linear/Integer programming algorithms.
Note (on @user53923's comment): There is a chance to get a path with a cycle, from the problem from the question, which is shortest including all vertices. But in this case we could check in polynomial time if the path has a cycle and if it has then simply reject. This would mean the graph does not have a Hamiltonian path, otherwise it would return it since its length would be shorter from that containing a cycle.
Note (on @user53923's comment): There is a chance to get a path with a cycle, from the problem from the question, which is shortest including all vertices. But in this case we could check in polynomial time if the path has a cycle and if it has then simply reject. This would mean the graph does not have a Hamiltonian path, otherwise it would return it since its length would be shorter from that containing a cycle.
Context
StackExchange Computer Science Q#81413, answer score: 4
Revisions (0)
No revisions yet.