Entering edit mode

7.0 years ago

m.malkowska
•
0

I'm stuck with this Rosalind problem. I'm trying to find time and memory efficient algorithm to compute the distance matrix from a weighted tree.

Input: a weighted tree with n leaves

Output: An n x n matrix (di,j) where di,j is the length of the path between leaves I and j

Sample Input

```
4
0->4:11
1->4:2
2->5:6
3->5:7
4->0:11
4->1:2
4->5:4
5->4:4
5->3:7
5->2:6
```

Sample Output

```
0 13 21 22
13 0 12 13
21 12 0 13
22 13 13 0
```

Any clues?

Thanks a lot!

Coming back to this years late unfortunately, but I think the Floyd-Warshall algorithm would be a poor choice for this, right? For a graph with V vertices, the algorithm is O(V^3), whereas this problem can be solved in O(V^2) for a binary tree. For example, for a binary tree with

nleaves:The two extremes are a perfectly balanced binary tree and a perfectly unbalanced (i.e., ladder-like) tree. In the case of a perfectly balanced binary tree, each level of the tree will perform a O(

n) operation, and there are O(logn) total levels, making the overall time complexity O(nlogn). For a perfectly unbalanced (i.e., ladder-like) tree, the internal nodes will performn+n-1 +n-2 + ... + 2 operations and each leaf will perform 1 operation (sontotal for all the leaves), so the overall time complexity will ben(n+1)/2 - 1 +n= O(n^2)