Help coderanch get a
new server
by contributing to the fundraiser
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Devaka Cooray
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• paul wheaton
• Henry Wong
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Tim Moores
• Carey Brown
• Mikalai Zaikin
Bartenders:
• Lou Hamers
• Piet Souris
• Frits Walraven

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

Enthuware Software Support
Posts: 4850
52
• Number of slices to send:
Optional 'thank-you' note:
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?

Ranch Hand
Posts: 87
• Number of slices to send:
Optional 'thank-you' note:
Run DFS on graph by visiting smallest node first, if there is a path, that would be the answer you are looking for.

Ranch Hand
Posts: 87
• Number of slices to send:
Optional 'thank-you' note:
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)

Saloon Keeper
Posts: 15705
367
• Number of slices to send:
Optional 'thank-you' note:
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: 4850
52
• Number of slices to send:
Optional 'thank-you' note:
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

Stephan van Hulst
Saloon Keeper
Posts: 15705
367
• Number of slices to send:
Optional 'thank-you' note:
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.

distancekey
01
12
14
23

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: 4850
52
• Number of slices to send:
Optional 'thank-you' note:
@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.

distancekey
01
14
15
23
32

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

Paul Anilprem
Enthuware Software Support
Posts: 4850
52
• Number of slices to send:
Optional 'thank-you' note:
Btw, I do have a solution but it is not too efficient.