CODEWITHSUNDEEP
c#algorithmdata-structuresgraph-theorydijkstra
Lars Holdgaard
Lars Holdgaard

Reputation: 9986

Shortest path while walking x unique nodes

I have a graph, where all my nodes have a calculated distance to each other.

Now, I want to start at my startNode, and then find the path with the lowest calculated value, as long as the path has X unique nodes. Think of it as a map: We start in Paris, and want to travel 3 cities. I want to find the path with 3 total stops away from Paris, with the lowest calculated value.

I am thinking of implementing a modified Dijkstra's algorithm, which normally would give me the shortest distance to an end destination, and then my end destinations is all X_level_out destinations, which should give me a running time of something like O(nodes^level) .

Does this make any sense? Are there any other suggestions?

Upvotes: 2

Views: 586

Answers (1)

Aditya
Aditya

Reputation: 5619

Given a weighted undirected graph G(V,E), and a set S subset of V find the Minimum-Cost tree that spans the nodes in S. This problem is known in the literature as the Steiner tree problem. The problem is NP-complete, which means that there is no known polynomial algorithm that will find the exact solution of the problem. However, there are algorithms that solve the Steiner problem in exponential time (O(2^N) or O(2^M)).

The Naive or Shortest Paths algorithm. 

Find the Shortest path tree from one participant node to the rest of the graph. 
Prune the parts of the tree that do not lead to a participant.

Complexity O(N^2), CR = O(M).

The Greedy or Nearest Participant First algorithm. (Takahashi, Matsuyama 1980) Start from a participant. 

Find the participant that is closest to the current tree. 
Join the closest participant to the closest part of the tree. 
Repeat until you have connected all nodes.

Complexity O(M N^2), CR = O(1), actually CR <= 2.

The Kou, Markowsky and Berman algorithm (KMB 1981). 

1. Find the complete distance graph G' 
  (G' has V' = S , and  for each  pair of nodes (u,v) in VxV there is an edge with weight equal to the weight of the min-cost path between these nodes p_(u,v)  in G) 
2. Find a minimum spanning tree  T' in G' 
3. Translate tree T' to the  graph G: substitute every edge of T', which is an edge  of G' with the corresponding path of G. Let us call T the result of the translation. 
4. Remove any possible cycles from T.

Complexity O(M N^2), CR = O(1), actually CR <= 2.

Upvotes: 2

Related Questions