Tag Archives: Widest path problem

Computer Algorithms: Minimum Spanning Tree

Introduction

Here’s a classical task on graphs. We have a group of cities and we must wire them to provide them all with electricity. Out of all possible connections we can make, which one is using minimum amount of wire.

To wire N cities, it’s clear that, you need to use at least N-1 wires connecting a pair of cities. The problem is that sometimes you have more than one choice to do it. Even for small number of cities there must be more than one solution as shown on the image bellow.

General Wiring Problem
 

Here we can wire these four nodes in several ways, but the question is, which one is the best one. By the way defining the term “best one” is also tricky. Most often this means which uses least wire, but it can be anything else depending on the circumstances.

As we talk on weighted graphs we can generally speak of a minimum weight solution through all the vertices of the graph.

By the way there might be more the one equally optimal (minimal) solutions. Continue reading Computer Algorithms: Minimum Spanning Tree