CODEWITHSUNDEEP
algorithmdata-structuresgraphminimum-spanning-tree
Marcus Kim
Marcus Kim

Reputation: 313

What is Dijkstra's Minimum Spanning Tree?

I'm having trouble finding an example algorithm for Dijkstra's Minimum Spanning tree. I already know about Dijkstra's Single Shortest Path algorithm, but not the spanning tree. I have the simple explanation from class which is this:

For each edge, add it to the tree. If a cycle is detected, remove the heaviest edge.

I've scoured the Internet and I couldn't find an algorithm for it.

I might need to just code it for myself, but I thought I would ask if anyone has a good example.

Can anyone help?

Upvotes: 4

Views: 1479

Answers (1)

clemens
clemens

Reputation: 17712

Here is a simple example:

enter image description here

The algorithm works as follows:

  1. The graph has gray edges.
  2. Adding some edges without detecting a circle.
  3. After adding the vertical edge, the algorithm detects a circle. It removes the last edge (red) because it has the heaviest weight.
  4. Adding the horizontal edge produces a circle, too. Since it has the heaviest weight it is removed.
  5. Adding the last edge will also produce a circle, but the last edge added hasn't the heaviest weight. Instead the edge with weight 3 must be removed. The Minimal Spanning Tree consists of the black coloured edges in picture (5).

If you are marking the visiting nodes, circle detection is easy. To find the heaviest edge of a detected circle, you use a common search algorithm for circles.

Note: Picture (5) demonstrates why it is necessary to visit all edges, because (3) already contains a Spanning Tree. But it is not minimal.

Upvotes: 5

Related Questions