Saturday, 23 Oct 2021

# Implementation of Johnson’s algorithm for all-pairs shortest paths

import java.util.ArrayList;import java.util.Arrays;  public class Graph {    private static class Neighbour {        int destination;        int weight;          Neighbour(int destination, int weight)        {            this.destination = destination;            this.weight = weight;        }    }      private int vertices;    private final ArrayList        adjacencyList;                  public Graph(int vertices)    {        this.vertices = vertices;          adjacencyList = new ArrayList(vertices);        for (int i = 0; i < vertices; i++)            adjacencyList.add(new ArrayList());    }                  public Graph(int vertices, int[][] adjacencyMatrix)    {        this(vertices);          for (int i = 0; i < vertices; i++) {            for (int j = 0; j < vertices; j++) {                if (adjacencyMatrix[i][j] != 0)                    addEdge(i, j, adjacencyMatrix[i][j]);            }        }    }      public void addEdge(int source, int destination,                        int weight)    {        adjacencyList.get(source).add(            new Neighbour(destination, weight));    }              public int[] dijkstra(int source)    {        boolean[] isVisited = new boolean[vertices];        int[] distance = new int[vertices];          Arrays.fill(distance, Integer.MAX_VALUE);        distance = 0;          for (int vertex = 0; vertex < vertices; vertex++) {            int minDistanceVertex = findMinDistanceVertex(                distance, isVisited);            isVisited[minDistanceVertex] = true;              for (Neighbour neighbour :                 adjacencyList.get(minDistanceVertex)) {                int destination = neighbour.destination;                int weight = neighbour.weight;                  if (!isVisited[destination]                    && distance[minDistanceVertex] + weight                           < distance[destination])                    distance[destination]                        = distance[minDistanceVertex]                          + weight;            }        }          return distance;    }          private int findMinDistanceVertex(int[] distance,                                      boolean[] isVisited)    {        int minIndex = -1,            minDistance = Integer.MAX_VALUE;          for (int vertex = 0; vertex < vertices; vertex++) {            if (!isVisited[vertex]                && distance[vertex]