12 ms·
>I have had to find minimum cost paths in a tree, though. Umm... every path is a minimum cost path in a tree, because there’s exactly one path between any two
by layoutIfNeeded 7y ago
>I have had to find minimum cost paths in a tree, though.
Umm... every path is a minimum cost path in a tree, because there’s exactly one path between any two vertices.
- deleted 7y ago[deleted]
- w8rbt 7y agoNon CS people may not understand this at first, but you are exactly right. A 'tree' is connected and has n-1 edges. So there can only be precisely one path between any pair of vertices. He may have meant a general connected graph (not specifically a tree). In which case, there could be multiple paths and some may be cheaper than others.
- geebee 7y agoThat’s a good guess/intuition - you’re correct that it wasn’t a binary tree strictly speaking. It was a situation where each node could activated by conditions on sub nodes, with a cost associated with activating each node. Also, in different scenarios, the tree would come with a different set nodes already activated. So the question was to figure out the minimum cost set of activations and in which order. It wasn’t a graph though as there was a unique path from the root to each leaf That’s about as well as I’m going to do here it was a while ago...