Heuristics: Minimal Spanning Tree 2: Unterschied zwischen den Versionen

Version vom 30. Juni 2013, 15:05 Uhr

Theory

Example

I would like to visit some of my friends in France this summer. But the road aren’t free in this country. Here are the cities I’d like to go and the cost of the use of every path.

To select the minimal cost path to join all of these, the construction of a minimal spanning is a solution to my problem. I can use either the kruskal's algorithm or the prim's algorithm to create it. Here is my solution with the minimal spanning tree. (To see the contruction of a minimal spanning tree in detail, go to "Detailed solution process with explanation")

Presentation of a problem

Consider the following communications network (Distance as evaluation of the edges)

We want to connect every system (node) with the others in the way that the distance between every system is minimal and there is only one way to go from one to another system. To do that, we can use 2 algorithms that have been explain before : Kruskal's and Prim's algorithm.

Detailed solution process with explanation

Kruskal's algorithm : With the Kruskal‘s algorithm, we have to list the existing link of our network in increrasing order. When two links have the same length, it doesn't have importance in which order they are. They only have to be together.

Sources

Radin, R. L. (1998): Optimization in Operations Research. New Jersey, Prentice Hall, pp 522-523.

W.Domschke,et al.,Übungen und Fallbeispiele zum Operations Research, 5th edition, 2005.