Tag Archives: shortest path

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

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