CODEWITHSUNDEEP
c#algorithmgraph
user1736516
user1736516

Reputation: 53

shortest path connecting certain nodes in an undirected graph

I have a certain subset of nodes of an undirected and unweighted graph. I am trying to determine whether there is a path between all of these nodes, and, if there is, what is the shortest path which includes the fewest nodes which are not in the subset of nodes.

I have been trying to think of a way to modify a minimum spanning tree algorithm to accomplish this, but so far I haven't come up with a workable solution.

Is there a good way to do this or is this a description of an already known algorithm?

Upvotes: 3

Views: 4283

Answers (6)

Alex Siepman
Alex Siepman

Reputation: 2598

I created a Graph/Node/Connection classes that not only shows you the shortest path but also can tell you if all nodes are connected:

var allNodesAreConnected = StartNode.AllNodes.All(n => n.IsConnectedToStartNode);

Or if you want to know what nodes are not connected change it a little bit:

var anotConnectedNodes = StartNode.AllNodes.Where(n => !n.IsConnectedToStartNode);

More examples and full code in this post: Create your own navigation system (with a Graph, Node and Connection class)

Upvotes: 0

Steve Westwood
Steve Westwood

Reputation: 131

For someone who doesn't really have a background in graph theory, I have tackled this problem and found that in an unweighted, undirected graph the easiest method is Depth First Search. Implementations of algorithms such as Dijkstra's often take a weighted solution and input an arbitrary value for the weight.

The solution I found to work I traversed nodes in using DFS and log every successful journey, then it's simply a case of returning the shortest successful journey.

Here's the file that does the heavy lifting: Depth First Search Algorithm

Upvotes: 0

Rusty Rob
Rusty Rob

Reputation: 17173

Here is an approach that may get you some of the way there:

Use Floyd-Warshall or Dijkstra's to find the distance d(i, j) between node i and node j for every i and j such that node i and node j are in the subset of nodes.

(if d(i,j) = infinity then stop now, there is no solution)

Make a new graph which contains each node from the subset. For each d(i, j), add an edge between node i, node j in the new graph with the weight = d(i, j)

Now use a traveling salesman algorithm on this new graph to find the shortest path to visit all nodes.

This shortest path gives you the length of the path but the path may visit some nodes multiple times. This means we have an upper bound on the number of nodes outside of the subset required.

Upvotes: 2

Evgeny Lazin
Evgeny Lazin

Reputation: 9413

You should use Dijkstra's shortest path algorithm. First, you must assign weights(or distances) to all edges in the graph, every edge that connects two nodes that are not in the subset must be given weight 1. Every edge that connects one or two nodes from the subset must be given infinite weight. Second, you should run Dijkstra's algorithm on the resulted graph. This algorithm will examine every edge of the graph.

Also, you can use A* (A-star) algorithm.

Update: I don't understand this problem at first. As @amit says, this is a NP-hard problem, a combination of HCP and TSP. Maybe some sort of stochastic search algorithm can solve this in polynomial time with high probability.

Upvotes: 0

amit
amit

Reputation: 178411

I am trying to determine whether there is a path between all of these nodes

(I understand from this you are looking for a single path that visits all the marked nodes)

Well my friend, this could be a problem - you are describing a variation of the Traveling Salesman Problem and the Hamiltonian Path Problem (If you are looking for a simple path, the reduction from Hamiltonian Path is straight forward: mark all the nodes).
But I am afraid these problems are NP-Hard.

An NP-Hard problem is a problem that we do not know of any polynomial time solution to solve it, and the general assumption around is - one doesn't exist1.

Thus, your best shot is probably going to be some exponential solution. There is O(n^2 * 2^n) solution to TSP using dynamic programming, or brute force solution which are O(n!)

(1) Really not a formal definition, but this is enough information to understand the problem, there is really a lot more into NP-Hard problems.

Upvotes: 2

iefpw
iefpw

Reputation: 7042

Dijkstra's algorithm or use a breadth first search.

Upvotes: 0

Related Questions