Let say we take the Prim’s algorithm for finding a minimal-spanning tree, which uses a minisming heap and changed it so that it uses a maximizing heap, will I be able to get a maximal spanning tree?
What I think is, yes, I would – the original Prim’s algorithim is a Greedy Algorithim. By snapping up all the vertices which are the furtherest away from the current MST, one shall be able to get a maximal spanning tree.
Am I right here? There seems to be something of a trap here…
Let me do an informal proof of Prim’s algorithm. (Assume all edge weights are unique. Easily done by modifying the edge compare algorithm. Also means the MST is unique.)
Say you were running Prim’s algorithm (more or less) and at some point you decided to skip the next min edge on the heap and continued building a spanning tree. Can the resulting tree be the MST?
Add in the edge you skipped. The former tree now has a cycle. At the time in Prim’s algorithm when you skipped over the edge, the tree did not have a cycle. Therefore, one of the other edges in the cycle was added after you skipped the edge. Therefore, its weight is larger than the one you skipped. So throw out that edge and you are back to a spanning tree with lower total cost.
Ergo, you didn’t have the MST.
So take the MST for your graph. Sort the edge weights. Run Prim’s algorithm. At the first point where the choice from Prim’s algorithm differs from the sorted edge list, apply the above logic to prove it isn’t the MST. Therefore there is no difference between the result of Prim’s algorithm and the MST.
Now think thru the proof replacing min with max, larger with smaller.
Yes, this I can understand.
My friend and I were thinking through this reasoning too. We got a graph, and run through the algorithim using a maxiziming heap. Since at every point when we choose a vertex, we choose the one with the largest weight, by the time we added all the vertices, we shall have all the maximum weight possible – which we can verify by removing one edge from the final maximal tree, and adding in one which we didn’t and check if the resultant weight is higher.
But as a sidenote – I doubt replacing the minimizing heap in Djikstra’ algorithm will provide a “longest path tree”. Reason is, well, the longest way from vertex A to vertex B is not the edge with the highest weight, but rather, a round-about way
Shortest paths is a different beast from MST. E.g., negative edge weights are not a problem for MST but can bust shortest paths.
Switching over to longest paths gets into NP-hard territory. E.g., even with edge weights all 1 and a fixed start and end point, finding the longest path from a to b is Hamiltonian Path.
(There’s an underlying field property necessary to be able to use general purpose algorithms like Prim or Floyd-Warshall. The operators in longest paths don’t meet it.)