Find diametre with the maximum cost in a tree

userWNKl1 0
Viewed 19

I have a weighted tree. How can I find the diameter with the maximum cost? For example, let's say I have a tree with 6 nodes such as:

  • the edge between 5 and 1 has a cost of 6

  • the edge between 6 and 1 has a cost of 7

  • the edge between 4 and 1 has a cost of 5

  • the edge between 6 and 3 has a cost of 9

  • the edge between 6 and 2 has a cost of 8

Then our answer is the path from 3 to 5 with a cost of 22

tree
1 Answers

You could:

  • Create an adjacency list from the given edges.
  • Choose any node as root and perform a depth-first traversal identifying the leaf with the most costly path from root to that leaf. That leaf will be one of the two nodes needed in the result.
  • Perform the same type of traversal but now with that leaf node as root. This results in a leaf with the most costly path from that root.
  • Return both nodes that were found and the cost that was determined in the second traversal.

Here is an implementation of that algorithm in JavaScript. It runs the algorithm on the example you have given:

function createAdjacencyList(edges) {
    const adj = {};
    for (const [begin, end, cost] of edges) {
        adj[begin] ??= [];
        adj[end] ??= [];
        adj[begin].push([end, cost]);
        adj[end].push([begin, cost]);
    }
    return adj;
}

function furthest(adj, start) {
    let maxCost = 0;
    let result = start;
    
    function dfs(parent, node, totalCost) {
        if (totalCost > maxCost) {
            result = node;
            maxCost = totalCost;
        }
        for (const [end, cost] of adj[node]) {
            if (end != parent) dfs(node, end, totalCost+cost);
        }
    }
    
    dfs(null, start, 0);
    return [result, maxCost];
}

function greatestDiameter(adj) {
    const anyNode = Object.keys(adj)[0];
    const start = furthest(adj, anyNode)[0];
    const [end, cost] = furthest(adj, start);
    return [start, end, cost];
}

// Demo
const edges = [
    [5, 1, 6], // from, to, cost
    [6, 1, 7],
    [4, 1, 5],
    [6, 3, 9],
    [6, 2, 8]
];

const adj = createAdjacencyList(edges);
const [start, end, cost] = greatestDiameter(adj);

console.log({start, end, cost});

trincot0
Related