Unique path between nodes

[Andrew Yang]

Suppose there are a bunch of nodes on a tree and between every two nodes there is a path with a unique length. Is there always one unique journey that travels through every node with minimal distance travelled. If yes, prove it. If no, give a counter-example. (Note: you can start at any node and don't include the reverse journey, since then there could be two unique journeys.)

 

[Dr.Peterson]

Please give an example of what this is saying, as you understand it, to make sure we're on the same page. I'm not quite sure what this means:

between every two nodes there is a path with a unique length

What does "unique" mean, as you are using it? What distinguishes one path or journey from another?

If you did not directly quote the problem you were given, please do so; and anything you can tell us about the context of the question (including what topics you are learning) can help us answer you.

 

[Andrew Yang]

Here's the question re-stated in a different way:
Think of this like a variation traveling salesman problem. You have a bunch of cities which are all connected with roads of unique arbitrary lengths (i.e. uncorrelated to the distance between the cities). Forget about their intersections (pretend that at every intersection one tunnels beneath the other). Now, is there a unique route (you can choose where you start) that goes to every city once which travels the shortest distance (disregard the reverse path as not making the route unique) or can there be multiple routes with the same shortest distance?
Note: You don't return to your starting city.
An additional wrinkle: Given this setup, is it possible for a greedy algorithm here to have the same distance as an opposite-greedy algorithm (i.e. takes longest paths)?

 

[Dr.Peterson]

Here's the question re-stated in a different way:
Think of this like a variation traveling salesman problem. You have a bunch of cities which are all connected with roads of unique arbitrary lengths (i.e. uncorrelated to the distance between the cities). Forget about their intersections (pretend that at every intersection one tunnels beneath the other). Now, is there a unique route (you can choose where you start) that goes to every city once which travels the shortest distance (disregard the reverse path as not making the route unique) or can there be multiple routes with the same shortest distance?
Note: You don't return to your starting city.
An additional wrinkle: Given this setup, is it possible for a greedy algorithm here to have the same distance as an opposite-greedy algorithm (i.e. takes longest paths)?

I think you are implying that this is not an exercise you were given, so the poor wording was your own.

It appears that you didn't really mean a tree, but a graph or network in general; you are not talking about a mere graph, but a weighted graph, with distances assigned (so that "length" doesn't just mean the number of edges traversed); and "path with a unique length" means (perhaps?) that no two edges have the same length.

What you are asking appears to be, then, is whether there can be more than one minimal Hamiltonian path under specified conditions. I can't say for sure, though it feels as though the solution may not always be unique. How much have you searched for information? Have you tried finding a simple counterexample?

 

[Andrew Yang]

Yeah, I was just playing around with some ideas and thought of this problem. You're right about everything in you second paragraph.
I was able to play around a bit and the shortest journey through all the cities is not always unique.
Now, I need help with this question: Given this setup, is it possible for a greedy algorithm (always takes the shortest edge) here to have a smaller distance than an opposite-greedy algorithm (always takes the longest possible path)? Note, you can start both algorithms off at any point you like in the graph (i.e. they don't have to have the same starting point.)

 

[Dr.Peterson]

Yeah, I was just playing around with some ideas and thought of this problem. You're right about everything in you second paragraph.
I was able to play around a bit and the shortest journey through all the cities is not always unique.
Now, I need help with this question: Given this setup, is it possible for a greedy algorithm (always takes the shortest edge) here to have a smaller distance than an opposite-greedy algorithm (always takes the longest possible path)? Note, you can start both algorithms off at any point you like in the graph (i.e. they don't have to have the same starting point.)

All I can say is, try it and see! That's a better way to learn a subject than asking someone for a ready-made answer, anyway.