Search⌘ K
Home
Courses
Mastering Algorithms for Problem Solving in Java

Challenge: Minimum Spanning Trees

Explore how to update a minimum spanning tree in an undirected weighted graph when the weight of a single edge is reduced. Learn to identify critical paths, find and replace the heaviest edge along the path, and implement this with Java code. Understand the underlying algorithms and their time complexity for effective graph problem-solving.

We'll cover the following...

Let's practice what we've learned so far.

Task

Suppose we’re given both an undirected graph GG with weighted edges and a minimum spanning tree TT of GG. Provide code to update the minimum spanning tree when the weight of a single edge ee is decreased. We can follow the algorithm described below.

Logic building

Here’s the algorithm to update the minimum spanning tree TT when the weight of a single edge ee is decreased:

Algorithm

  • Identify the two nodes uu and vv that the edge ee connects.
  • Find the path PP in the minimum spanning tree
...