Maximum spanning tree (${\max }_T{\sum }_{e\in T}w(e)$)

A spanning tree with greatest total edge weight. Apply Kruskal's algorithm in decreasing weight order, or negate every edge weight and compute a minimum spanning tree. Every graph path within a maximum spanning tree solves the widest path problem between its endpoints.