Graphs Algorithm
Johnson's Algorithm

Johnson's Algorithm

Johnson's Algorithm is a method used to find the shortest paths between all pairs of vertices in a weighted graph. It improves on the Floyd-Warshall Algorithm by using a reweighting scheme and the Bellman-Ford Algorithm to efficiently solve the All-Pairs Shortest Path (APSP) problem.

How Johnson's Algorithm Works

  1. Graph Transformation:

    • Augment the original graph by adding a new vertex and edges with weight 0 to all other vertices.

  2. Edge Re-Weighting:

    • Apply the Bellman-Ford Algorithm on the augmented graph to find the minimum weight of all paths from the newly added vertex to every other vertex.
    • Reweight the edges in the graph using the minimum weights obtained.

  3. Shortest Path Calculation:

    • Run Dijkstra's Algorithm for each vertex as the source to find the shortest paths to all other vertices.

  4. Reversing the Transformation:

    • Restore the original weights by undoing the reweighting process to obtain the shortest paths.

Key Features

  • Optimized for Sparse Graphs: Johnson's Algorithm is more efficient for sparse graphs than the Floyd-Warshall Algorithm.
  • Utilizes Bellman-Ford and Dijkstra: It combines the Bellman-Ford and Dijkstra's Algorithms for the APSP problem.

Efficiency

  • Time Complexity: Johnson's Algorithm's time complexity depends on the Bellman-Ford and Dijkstra's Algorithms, making it (O(V * E \log V)).
  • Space Complexity: It has a space complexity of (O(V + E)), where V is the number of vertices and E is the number of edges in the graph.

Applications

  • Routing Algorithms: Johnson's Algorithm is used in computer network routing protocols to determine the best path between devices.
  • Optimization Problems: It's applied in transportation and logistics to optimize routes for vehicles.
  • Network Analysis: Johnson's Algorithm aids in understanding network properties like centrality and connectivity.

Limitations

  • Computational Complexity: Despite being more efficient than some algorithms, it can be computationally intensive for large graphs.
  • Sparse Graphs Benefit More: It's more suitable for graphs with sparse edge connections than for denser graphs.

Johnson's Algorithm Implementation in JavaScript

Here's an explanation and example of implementing Johnson's Algorithm in JavaScript:

Searching-Algo/jhns.js
// Johnson's Algorithm
function johnsonsAlgorithm(graph) {
    // Step 1: Graph Transformation
    const newVertex = 'newVertex';
    graph.addVertex(newVertex);
    graph.vertices.forEach(vertex => {
        graph.addEdge(newVertex, vertex, 0);
    });
 
    // Step 2: Edge Re-Weighting
    const distances = bellmanFord(graph, newVertex);
    graph.edges.forEach(edge => {
        edge.weight += distances[edge.vertex1] - distances[edge.vertex2];
    });
 
    // Step 3: Shortest Path Calculation
    const shortestPaths = {};
 
    graph.vertices.forEach(vertex => {
        const dijkstraDistances = dijkstra(graph, vertex);
        shortestPaths[vertex] = {};
 
        graph.vertices.forEach(v => {
            shortestPaths[vertex][v] = dijkstraDistances[v] + distances[v] - distances[vertex];
        });
    });
 
    // Step 4: Reversing the Transformation
 
    return shortestPaths;
}
 
// Bellman-Ford Algorithm
function bellmanFord(graph, startVertex) {
    const distances = {};
 
    graph.vertices.forEach(vertex => {
        distances[vertex] = vertex === startVertex ? 0 : Number.MAX_SAFE_INTEGER;
    });
 
    for (let i = 0; i < graph.vertices.length - 1; i++) {
        graph.edges.forEach(edge => {
            if (distances[edge.vertex1] + edge.weight < distances[edge.vertex2]) {
                distances[edge.vertex2] = distances[edge.vertex1] + edge.weight;
            }
        });
    }
 
    return distances;
}
 
// Dijkstra's Algorithm
function dijkstra(graph, startVertex) {
    const distances = {};
    const visited = {};
    const queue = [];
 
    graph.vertices.forEach(vertex => {
        distances[vertex] = vertex === startVertex ? 0 : Number.MAX_SAFE_INTEGER;
        visited[vertex] = false;
        queue.push(vertex);
    });
 
    while (queue.length !== 0) {
        let u = queue.reduce((min, vertex) => (distances[vertex] < distances[min] ? vertex : min), queue[0]);
        queue = queue.filter(v => v !== u);
 
        visited[u] = true;
 
        graph.edges.forEach(edge => {
            if (edge.vertex1 === u && !visited[edge.vertex2]) {
                const alt = distances[u] + edge.weight;
                if (alt < distances[edge.vertex2]) {
                    distances[edge.vertex2] = alt;
                }
            }
        });
    }
 
    return distances;
}
Floyd WarshallKruskal's Algorithm