Tuesday, November 10, 2009

MST-TSP-TOUR Clarifications/Hint

Sorry for the delay in getting these up! There seems to be a lot of confusion in how to do MST-TSP-TOUR, so I wanted to officially make a few clarifications. (1) The graph you recieve will not necessarily be complete. This is the point of "completing the graph." To "complete the graph" your edges in the graph should be minimal path weights. This is convieniently where Dijkstra comes in. (2) To deal with a subset of vertices, you should just make a complete graph ON THOSE VERTICES, before creating an MST ON THOSE VERTICES. (3) The vertices in the list that you return represent a list of destinations. Imagine that you are at the vertex you want to start from. The list of vertices tells you where to go next. So, as a result of this, the first vertex in the list is NOT the goal, but the last is. Hope that helps! --Adam