What are the differences between the widest path and longest path questions? More specifically, why can the former be solved by finding the maximum spanning tree whereas the latter cannot. I know in drawing out the maximum spanning tree it's immediately obvious that it does not necessarily contain the longest path, but I can't wrap my mind around what the differences are between the two questions that make this fact true.
Thanks.
The main difference between these two problems is that the widest path problem exhibits optimal substructure while the longest path problem (to the best of anyone's knowledge) doesn't.
Specifically, consider the widest path from a node u to a node v. If that path passes through an intermediary node s, then the widest path from u to v must consist of a widest path from u to s followed by a widest path from s to v. If it didn't, then you could replace either part of the path from u to s or from s to v with an even wider path without making the solution any worse.
However, this doesn't work for the longest path problem. If you take the longest path (implicitly, the longest simple path) from u to v and it passes through some node s, you do not necessarily have the longest path from u to s followed by the longest path from s to v. Here's an example:
2
u --- v
1 \ / 3
s
The longest path from u to s consists of the path u - v - s (length 5), while the longest path from u to v is u - s - v (length 4).
This optimal substructure property makes it possible to use greedy algorithms and (efficient) dynamic programming to solve the widest path problem efficiently but (to the best of anyone's knowledge) not possible to solve the longest path problem efficiently. You can make a similar argument about shortest paths, by the way (if the shortest path from u to v passes through s, you have the concatenation of the shortest paths from u to s and from s to v), and you can use similar greedy algorithms or DP to determine shortest paths as well.
Hope this helps!