CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
Moustafa Mahmoud
Moustafa Mahmoud

Reputation: 21

Getting Paths that cover all the nodes and Start and End at Special Nodes

I have this graph problem where i have a number of Nodes (bus stops ) and some Special nodes (Bus Stations) , I have to cover all the Nodes - Assign bus routes that cover all of them - while starting and ending at a station and I have some restrictions on number of busses I can use , Any ideas how I should start?

Upvotes: 0

Views: 1414

Answers (2)

amit
amit

Reputation: 178531

The problem of finding the shortest path that connects all nodes (with the bus stations restriction) is reduceable from the Traveling Salesman Problem with the reduction of: given a TSP problem, create an instance of this problem with 1/2 stations/"special nodes" (depending weither or not you can come back to the same station).

Using this reduction - if this problem is solveable polynomially - so is TSP.

Thus - the problem is NP-Hard, and there is no known polynomial solution to it (and the assumption is - one does not exist, though it is not proven yet)

Some alternative are heuristic algorithms such as Genetic Algorithm and Hill Climbing, approximation algorithms, or exponential algorithms (which can be used to find an optimal solutions if the data is relatively small) like Dynamic Programming or branch and bound.

EDIT: (response to edited question)

Even if you can use several buses - but a limited number of them - the problem is still NP-Hard, because (assuming the number of buses is constant/given in unary coding): you can "duplicate" the graph to k distinct components (where k is the limited number of buses) - and you have yourself a new TSP problem for each component.

Upvotes: 1

Samy Arous
Samy Arous

Reputation: 6812

Here's a simple idea:

  1. Remove the start and end node from the graph.
  2. Search for the minimum spanning tree
  3. Connect the start-end node to the spanning tree.

With that you can have a minimal cover solution.

Of course, if you need to visit each node once, then as stated, this is an NP-Hard problem.

Upvotes: 0

Related Questions