Tag Archives: Greedy Algorithm

Prim’s Algorithm

Prim’s algorithm searches minimum spanning tree in a weighted undirected graph. In other words, it finds a sub-set of edges that forms a tree, where all vertices of a given graph are included and total weight of all edges is minimized.

Let’s consider the following example. You are an engineer and you’re going to build electrical grid to provide electricity to all houses bellow. The weight represents distance between two houses.

pa_main_1

Of course, the houses can be connected in a random way and the problem will be solved. Continue reading Prim’s Algorithm

Kruskal’s Algorithm

Kruskal’s algorithm is used to find minimum spanning tree in a weighted undirected graph. A spanning tree of a undirected graph G is a sub-graph that includes all vertices of G and satisfies conditions of a tree. On the diagram below you can find two graphs and only left graph can be considered as spanning tree.

span_tree_1

Because, the right graph has a cycle and this fact violates condition which states that a tree cannot have a cycle.  Continue reading Kruskal’s Algorithm

Dijkstra’s algorithm

Searching the shortest path between two vertices is a very common problem when you are dealing with graphs. This problem can be solved by various algorithms and in this article I will try to describe Dijkstra’s algorithm DA. But first, I would like to show you a shortest path in an arbitrary graph.

sp_!

As you can see, the shortest path has minimal sum of all weights of its constituent edges. A path can occur in either directed or undirected graphs. Continue reading Dijkstra’s algorithm