CODEWITHSUNDEEP
algorithmgraphdijkstra
skillness
skillness

Reputation: 31

How to find a shortest path in a directed graph which must pass through specific nodes?

I have a directed graph with less than 600 nodes, and each node's edge number is less than 8. Now I need to find a path in this graph which must pass through some given nodes(<50). The order of passing given nodes is free. I know it's a NPC problem, but I don't know how to solve it. An approximate solution is also acceptable. Thank you!

Upvotes: 2

Views: 870

Answers (1)

Aziuth
Aziuth

Reputation: 3902

Compute the shortest ways between all pairs of the specific nodes. Then create a new graph that only contains those nodes, with the length of the shortest paths as distances. Now, the problem is "reduced" to Travelling Salesman.

(TSM has a fast 3/2-approximation that utilitizes minimal spanning trees and a matching, if that is good enough - the 50! possibilities are too much in any case)

Upvotes: 1

Related Questions