Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
Finding an exact solution to the optimization TSP requires factorial, O(n!), time using a brute-force solution - enumerating all possible tours and determining their respective distances - and O(n^2 * 2^n) using a dynamic programming approach.
Generally, people use approximation algorithms to find an answer to an instance of a TSP that is "good enough." For specific versions of the TSP (such as the Euclidean TSP), there exists an approximation that is guaranteed to be within certain bounds of the actual minimum tour which can be done in polynomial time, in this case, the Polynomial Time Approximation Scheme (PTAS) for 2-Dimensional Euclidean TSP.
Do we use a combination of Dijkstras and Minimum Spanning Tree using Prims?, use Minimum Spanning Tree to go through all the nodes once, after that use Dijkstras to come back to the start node from the end node?, this might not be the best shortest path around, but an approximation of shortest path around.
You can use Dijkstra for TSP graph where each edges only visit vertices once. For example, A->B->C->D->A. Or even if there's an additional edge from B->D but the weight is bigger than A->D.
I think it's not possible to use Dijkstra for any graph since Dijkstra complexity is E+VLogV, and TSP is NP.
In regular Dijkstra you choose the next edge as the one that's nearest to the source, and not already part of the tree. Well, instead of keeping track of used nodes by the whole tree, keep them by individual path (when you branch in 2nd direction from a node, you'll have to make a new path). When you check for where to extend your edge to, check only that it doesn't touch your current own path (grrr - there may be more than one way to get to that node, thus more than one path. No, we got here the shortest way possible, no?). Anyway, first you remove the source from all paths, so that it's ok to add it. When you add a node, see if it's the source, and if so see whether your path includes all nodes. If so, this should be a shortest path. If not, abandon this path. Not 100% sure this works though. And, it's not really the Dijkstra algorithm anymore, it's just similar - is this really the question?
You would not use Dijkstra's algorithm to solve the traveling salesman problem. Dijkstra's algorithm solves the single-source shortest path problem which gives the shortest path to each node from a singular starting node. Dijkstra's algorithm would be useful if it was necessary to go to each city and return back to the start after each trip.
- Evan February 06, 2014You could, from the start node, determine the next shortest path to another node, i.e. the next closest node (taking care to not visit any nodes that had previously been visited), and continue this for each node until back to the start, but the simple greedy algorithm does not guarantee that you will get the overall shortest path from start to finish (and back to start).