Tag Archives: graph

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

Johnson’s Algorithm

Johnson’s algorithm solves the all-pairs shortest path problem on a graph which may contain negative weight but has no negative weight cycle. In other words, it searches for the shortest distance between every pair of vertices in a given directed graph. The algorithm uses Bellman-Ford algorithm to prepare graph for re-weighting.

The re-weighting technique changes all negative weights to nonnegative. Thus,  once we get rid of all negative weights we can use Dijkstra’s algorithm that is faster than Bellman-Ford algorithm to obtain shortest path between all pair of vertices.

Before, we run Bellman-Ford algorithm we need to add a new vertex and connect it to all others with zero weight.

john_1

As result we have a vertex from which every node can be accessed and now it is time run Bellman-Ford algorithm from this new node. Continue reading Johnson’s Algorithm

Bellman-Ford Algorithm

The Bellman-Ford algorithm solves single-source shortest path problem in a directed graph with negative and positive  weights. Its time complexity in worst case is equal to Ο(V*E) while Dijkstra’s algorithm has Ο((V+E)log V) time complexity. Thus, if you don’t have negative weights it’s preferable to use Dijkstra’s algorithm.

The only problem that can occur during execution of Bellman-Ford algorithm is  a negative weight cycle. It is a cycle with weights that sum to a negative number. In that case the algorithm relaxes its nodes indefinitely. Fortunately, Bellman-Ford algorithm can detect negative weight cycle.

nwcg

The algorithm was discovered independently by Richard Bellman and Lester Ford, Jr. Continue reading Bellman-Ford 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

Strongly Connected Components

Another useful application of the depth-first search algorithm, is decomposing of the directed graph into the strongly connected components or SCC. A strongly connected component of the graph is a maximal set of vertices in which there is a path from any vertex to any other vertex in both directions.

scc4

The above directed graph has three strongly connected components. Continue reading Strongly Connected Components