Johnson’s Algorithm
In a directed graph, this very algorithm finds out the shortest paths between all the given pair of vertices, this functioning algorithm is known to be as the Johnson’s Algorithm.
The way it works is that it converts the edge weights that are negative into non-negative edge links, following a very specific method.
> Firstly, using the Bellman Ford algorithm to clear all the weights that are negative
> Then secondly, using Dijkstra’s algorithm on the following new graph.
NOTE: There are other algorithms that could be used here like the Floyd Warshall but it’s Time Complexity is Θ(V3), here when we proceed with Johnson, it takes O(V²log V + VE) time to find the shortest paths.
As mentioned above, Johnson’s algorithm is a mixture of both algorithms — Bellman-Ford and Dijkstra.
But Dijkstra algorithm takes less time to find the shortest paths, so why not use it?
Considering every vertex as source, Dijkstra takes only O(V²LogV) time to find all pairs of shortest path, so it is anyway a better option than Floyd Warshell but there’s a shortcoming to this algorithm that this doesn’t work on negative weight edges.
So then finally the idea of Johnson Algorithm popped out, where all the edges would be re-weighted and converted positive and then Dijkstra’s algorithm would be applied.
UNDERSTANDING ALGORITHM:
To understand the algorithm, we will proceed with an example having negative edges so that Dijkstra’s algorithm couldn’t be applied directly to the starting points.
Here, we will assume that each point x possess a weight f(x):
Now, changing the new edge weight as:
new_edge(p,q)=edge(p,q)+f(p)-f(q)
Going on, D(x,y) is the distance that goes from several nodes, the total weight that would come would be:
NOTE: (here, the starting and ending point remians unchanged, which also means that the size of total weight of contrasting remains unchanged as well)
new_D1(x, y) = new_edge(x,p) + new_edge(p,q) + new_edge(q,y)
= [E(x,p)+h(x)-h(p)] + [E( p,q)+h(p)-h(q)] + [E(q,y)+h(q)-h(y)]
= E(x,p) + E(p,q) + E (q,y) + h(x)-h(y)new_D2(x, y) = new_edge(x,r) + new_edge(r,s) + new_edge(s,y)
= E(x,r) + E(r,s) + E(s,y) + h (x)-h(y)new_D3(x, y) = new_edge(x,t) + new_edge(t,y)
= E(x,t)+ E(t,y) + h(x)-h(y)
Moving further, adding to all the points, a starting point and making the edge(s,x)=0 and finding the shortest path of all the consisting D(s,x) with the help of Bellman-Ford algorithm and then making the f(x) = min(D(s,x).
Concluding from the mentioned point, the paths that pass through edge(p,q) can then become non negative paths when the value of +f(p)-f(q) is then adjusted.
PSEUDO CODE AND IDEA:
The idea of Johnson’s Algorithm is also based on a Lemma which is quoted below:
If a digraph D= (V,A) has a vertex s such that all vertices are reachable from s,then φ(v) = dist(s,v)is a feasible potential for D
Feasible potential is something which gives each vertex a carefully chosen weight φᵥ.
DEFINITION: For a weighted digraph G= (V,E), a functionφ:V→R is a feasible potential if for all edges e= (u,v)∈ E φ(u) +wᵤᵥ−φ(v)≥0.
Now after assigning a feasible potential, each weight could be set to:
wᵤᵥ to ˆwᵤᵥ : = wᵤᵥ+φ(u)−φ(v)
And now for all the edges, wᵤᵥ>0, we imply that the feasible potential would be φ(v) = 0.
And then setting a φ(s) = 0 for some vertex s:
Psuedo code:
Input: A weighted digraph D= (V,A)
Giving output as, for D, listing all the pairs of shortest paths.
V′←V∪{s}
/* add a new source vertex */
A′←E ∪ {(s,v,0)|v∈ V/};
Dist←Bellman Ford((V′,A′));
/* feasible potentials*/
for e= (u,v)∈ A do
weight(e)+ =D(u)−D(v);
end
L= []/* the result */
for v∈V do
L+ = Dijkstra(D,v);
end
return L;
DRAWING COMPARISONS:
In graph theory, the Shortest Path Algorithm is an important problem and has vast spectrum of applications overall, so it’s important to have the best fitted algorithms suitable to situations.
So drawing the comparison of Johnsons’ to other algorithms:
Johnson’s works on Negative edges and All sources with a time complexity of O(VE+V²lgV) whereas Bellman-Ford works on Negative edges and Single Source only with a time complexity of O(VE).
Now since, Johnson’s is a mix of Bellman-Ford and Dijsktra, comparing both of them in the following figure.
In certain use cases, Johnson’s have an upper edge whereas in cases like when the graph is quite dense, algorithms like Floyd-Warshall fare better than the Johnson’s algorithm. But in case of Sparse-graphs, Johnson’s algorithm is faster than Floyd-Warshall giving it a more pick rate in problems of Sparse graphs.
TIME COMPLEXITY:
Since, the algorithm uses the Bellman-Ford as the first step, taking a time of O(V E); and reweighing all the edges requires a per-processing cost of O(E).
After that, Dijkstra’s algorithm is run, making the time complexity of this particular step as O(VE+V²lgV)
Then again, reweighing the shortest paths for each pair, taking a O(V²) time.
In total, this algorithm takes a time of O(VE+V²lgV)
CONCLUSION:
All in all, the Short Path Algorithm is of very much importance and the algorithms that optimize and solve this problem open up a lot of applications in the industry and complex problems, so according to the mentioned conditions and situations, an appropriate algorithm like Johnson’s could be applied which already is a standard.
