Forum:

Programming Diversions

Is this a variation of Shortest path problem or a different class of problem?

Enthuware Software Support

Posts: 4828

posted 11 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

In a classic shortest path problem, you need to minimize the sum of edge weights. Dijkstra's is one the algorithms that can find it.

What if you have to traverse a graph from node 1 to node N such that the sequence of the nodes visited is smallest possible sequence when compared numerically with any other sequence. For example, sequence 1 2 3 is smaller than 1 3 2.
Of course, if every node is connected to every other node, the sequence would be 1, 2, 3, 4, ..., N. But what if some edges are missing?

I am not sure what is this class of problems called and where there are any well known algorithms to find such a path?

Any thoughts?

Enthuware - Best Mock Exams and Questions for Oracle Java Certifications
Quality Guaranteed - Pass or Full Refund!

Bhaskar Bantupalli

Ranch Hand

Posts: 87

I like...

posted 11 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Run DFS on graph by visiting smallest node first, if there is a path, that would be the answer you are looking for.

Bhaskar Bantupalli

Ranch Hand

Posts: 87

I like...

posted 11 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Are you looking for a sequence that connects(without repeating edges and self loops) and not worried about the path sum?
If yes, DFS.
But if you are looking for shortest path sum and then shortest path sequence among those equal paths, then Djikstra with PrioityQueue having least weight and then least edge index as high priority. The comparator will take care of it.(Djikstra conditions apply-positive edge weight)

Bhaskar Bantupalli

Stephan van Hulst

Saloon Keeper

Posts: 15608

366

posted 11 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Yes, this is pretty much shortest path, but with every edge weight replaced by the key of the destination node. The challenge lies in the fact that the weights are not fixed during the search, but depend on which of the two connected nodes is the origin, and which the destination.

You can probably use A* search to find the shortest path very efficiently. You just need to think carefully on how to implement the heuristic.

Paul Anilprem

Enthuware Software Support

Posts: 4828

posted 11 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Yes, you are right. But now that I am thinking about it more I realize that the problem is not too interesting. Let me make it a little more complicated
Let's say you have 4 nodes with bidirectional edges as shown in the image.

You are at node 1 and your goal is to visit all of the nodes. So, for example, you could take this path:
1 2 1 4 3
or
1 4 3 4 1 2

Further, let's say I want to omit printing the node that I have already visited. So, for the above two routes, I will print:
1 2 4 3
and
1 4 3 2

Now, between the above two sequences, the first sequence 1 2 4 3 is preferable to the second one 1 4 3 2 because 1 2 4 3 is is smaller (if compared lexicographically as a whole) .

test.png

Enthuware - Best Mock Exams and Questions for Oracle Java Certifications
Quality Guaranteed - Pass or Full Refund!

Stephan van Hulst

Saloon Keeper

Posts: 15608

366

posted 11 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Seeing as visiting a node a second time is free, the problem devolves to finding the distance of every node, and then ordering them by distance first, and then key second.

distance	key
0	1
1	2
1	4
2	3

You'd do this by using Dijkstra's algorithm to get the shortest path tree for the entire graph, and then just sorting the results.

Paul Anilprem

Enthuware Software Support

Posts: 4828

posted 11 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

@stephen, may be I understood you incorrectly, but I am not sure your approach will work. Consider the graph with 5 nodes as shown in the image.

As your your approach the distances are:

distance	key
0	1
1	4
1	5
2	3
3	2

So, your approach will produce, 1, 4, 5, 3, 2
But the correct sequence should be 1, 4, 3, 2, 5 because this sequence is smaller.

test2-(2).png

Enthuware - Best Mock Exams and Questions for Oracle Java Certifications
Quality Guaranteed - Pass or Full Refund!

Paul Anilprem

Enthuware Software Support

Posts: 4828

posted 11 months ago

Number of slices to send:

Optional 'thank-you' note:

Send

Btw, I do have a solution but it is not too efficient.
1. Start with node 1.
2. Pick the next smallest unvisited node (node 2, in this case), and see if you have a path from any of the previously visited nodes to this node. If yes, visit this node, if not, pick the next smallest node and repeat the process.
3. As soon as you visit a node, go back to step 2.
4. Repeat until all nodes are visited.

Step 3 is inefficient because it requires checking for the existence of a path from the same source/destination multiple times.

Enthuware - Best Mock Exams and Questions for Oracle Java Certifications
Quality Guaranteed - Pass or Full Refund!

Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?