CODEWITHSUNDEEP
graphdijkstra
Moroianu Alexandru
Moroianu Alexandru

Reputation: 167

Find the starting node such that will get shortest path by passing through specific nodes

I have an undirected graph with at most 10 000 nodes and 50 000 edges . I need to find the node in which i should start such that passing through some mustpass nodes the distance will be the shortest.

I was thinking at applying Dijkstra between the nodes of the graph , but i don't know how to select the best starting node.

The mustpass nodes may be visited in any order.

Upvotes: 0

Views: 314

Answers (1)

yurib
yurib

Reputation: 8147

sounds like a version of the Traveling Salesman Problem which is NP-Hard so no simple and quick solution exist for it.

you could try to find sub-optimal solutions using heuristics and aproximation algorithms, also, since you only need to visit a subset of the nodes, you could limit your search to those.

Upvotes: 1

Related Questions