DEPARTMENT OF COMPUTER SCIENCE
AND ENGINEERING
DATA STRUCTURES AND ALGORITHMS FOR
PROBLEM SOLVING(MCS103)
TOPIC: JOHNSON’S ALGORITHM FOR SPARSE GRAPHS
PRESENTED BY: GUIDED BY:
DEEPTHI K:1KS24SCS02 DR. VIJAYALAXMI MEKALI
ASSOCIATE PROFESSOR,
K S INTITUTE OF TECHNOLOGY
KANAKAPURA ROAD, BENGALORE
Introduction
• Johnson’s Algorithm is used to find the shortest paths between all
pairs of vertices in a weighted graph.
• Works efficiently for sparse graphs (graphs with fewer edges).
• Handles graphs with negative weights (but no negative cycles).
Why Johnson’s Algorithm?
• Combines Bellman-Ford and Dijkstra’s Algorithm.
• Works well for graphs where |E| ≈ |V|, making it more efficient than
Floyd-Warshall.
• Runs in O(V^2 log V + VE) time.
• Can process graphs with negative weights unlike Dijkstra’s alone.
• The idea of Johnson’s algorithm is to re-weight all edges and make
them all positive, then apply Dijkstra’s algorithm for every vertex.
Algorithm
• Let the given graph be G. Add a new vertex s to the graph, add edges
from the new vertex to all vertices of G. Let the modified graph be G’.
• Run the Bellman-Ford algorithm on G’ with s as the source. Let the
distances calculated by Bellman-Ford be h[0], h[1], .. h[V-1]. If we find
a negative weight cycle, then return. Note that the negative weight
cycle cannot be created by new vertex s as there is no edge to s. All
edges are from s.
• Reweight the edges of the original graph. For each edge (u, v), assign
the new weight as “original weight + h[u] – h[v]”.
• Remove the added vertex s and run Dijkstra’s algorithm for every
vertex.
Algorithm
• We add a source s and add
edges from s to all vertices of
the original graph. In the
following diagram s is 4.
Algorithm
• We calculate the shortest
distances from 4 to all other
vertices using Bellman-Ford
algorithm. The shortest
distances from 4 to 0, 1, 2 and 3
are 0, -5, -1 and 0 respectively,
i.e., h[] = {0, -5, -1, 0}. Once we
get these distances, we remove
the source vertex 4 and reweight
the edges using following
formula. w(u, v) = w(u, v) + h[u]
– h[v].
Algorithm
• Since all weights are positive
now, we can run Dijkstra’s
shortest path algorithm for
every vertex as the source.
• Reweight the graph using
Bellman-Ford.
• Run Dijkstra’s Algorithm for
each vertex.
• Adjust shortest path distances
back to original weights.
Step 1 - Reweighting Using Bellman-Ford
• Add a new vertex s and connect it to all vertices with weight 0.
• Run Bellman-Ford from s to detect negative cycles.
• If no negative cycles, calculate h(v) values using the shortest paths
from s.
Step 2 - Running Dijkstra’s Algorithm
• Modify edge weights using h(v) values: w’(u, v) = w(u, v) + h(u) - h(v).
• Run Dijkstra’s Algorithm from each vertex v to get shortest paths in
O(V log V + E) time.
Step 3 - Adjusting Shortest Paths
• Convert computed shortest paths back to the original weight scale:
• d(u, v) = d’(u, v) - h(u) + h(v)
• This restores correct shortest path values while keeping non-negative
weights during processing.
Complexity Analysis
• Bellman-Ford: O(VE)
• Dijkstra’s (V times with a min-heap): O(V^2 log V + VE)
• Total Complexity: O(V^2 log V + VE), efficient for sparse graphs.
Applications of Johnson’s Algorithm
• Network Routing - Finding shortest paths in communication
networks.
• Transportation Systems - Optimizing road networks with varying
traffic conditions.
• AI and Game Development - Pathfinding in large sparse maps.
