ABSTRACT
In this chapter, we present algorithms to perform computations on a weighted graph in terms of the WeightedGraph interface. This allows any graph representation to be used. We include the following algorithms:
Greedy Tree Builder: We present a general greedy algorithm for constructing a tree. This algorithm can be instantiated to solve a variety of problems including the single-source shortest path problem, the minimum spanning tree problem, and the maximum bottleneck problem (page 927). When using an adjacency list for the graph representation and using a Fibonacci heap (Chapter 28) for the tagged priority queue, the tree builder method has worst-case asymptotic time complexity O(m+ n log n).
