minimum weighted path length

Given a list of weights, W:={w1,w2,,wn}, the minimum weighted path length is the minimum of the weighted path length of all extended binary treesMathworldPlanetmath that have n external nodes with weights taken from W. There may be multiple possible trees that give this minimum path length, and quite often finding this tree is more important than determining the path length.


Let W:={1,2,3,3,4}. The minimum weighted path length is 29. A tree that gives this weighted path length is shown below.


Constructing a tree of minimum weighted path length for a given set of weights has several applications, particularly dealing with optimization problems. A simple and elegant algorithmMathworldPlanetmath for constructing such a tree is Huffman’s algorithm. Such a tree can give the most optimal algorithm for merging n sorted sequences (optimal merge). It can also provide a means of compressing data (Huffman codingMathworldPlanetmath), as well as lead to optimal searches.

Title minimum weighted path length
Canonical name MinimumWeightedPathLength
Date of creation 2013-03-22 12:32:12
Last modified on 2013-03-22 12:32:12
Owner mathwizard (128)
Last modified by mathwizard (128)
Numerical id 6
Author mathwizard (128)
Entry type Definition
Classification msc 05C05
Related topic WeightedPathLength
Related topic ExtendedBinaryTree
Related topic HuffmansAlgorithm
Related topic HuffmanCoding