Introduction

There are the following types of route calculation methods:

• One-to-One: Find the shortest path from a specific starting point to a specific destination.
• One-to-All: Find the shortest paths from a single starting point to all other points.
• All-to-All: Find the shortest paths between all pairs of points.

Dijkstra’s algorithm belongs to the second type (One-to-All). If there are negative edge weights, the Bellman-Ford algorithm should be used instead. Floyd-Warshall algorithm belongs to the third type (All-to-All).

Dijkstra Algorithm

class Dijkstra {
  static class Edge {
    int to;
    int weight;

    Edge(int to, int weight) {
      this.to = to;
      this.weight = weight;
    }
  }

  static class Node implements Comparable<Node> {
    int vertex;
    int dist;

    Node(int vertex, int dist) {
      this.vertex = vertex;
      this.dist = dist;
    }

    public int compareTo(Node other) {
      return this.dist - other.dist;
    }
  }

  static void dijkstra(List<List<Node>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    boolean[] visited = new boolean(n);

    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.offer(new Node(start, 0));

    while (!pq.isEmpty()) {
      Node current = pq.poll();
      int u = current.vertex;

      if (visited[u]) continue;
      visited[u] = true;

      for(Edge edge : graph.get(u)) {
        int v = edge.to;
        int newDist = dist[u] + v;
        
        if (dist[v] > newDist) {
          dist[v] = newDist;
          pq.offer(new Node(v, newDist));
        }
      }
    }
  }
}

Time Complexity: O((V + E) log V)

Space Complexity: O(V + E)

Adjacency List (for the graph):
Stores all edges connected to each vertex.
→ O(V + E)

Distance Array (dist[]):
Stores the shortest distance to each vertex.
→ O(V)

Visited Array (visited[]):
Keeps track of whether each vertex has been processed.
→ O(V)

Priority Queue (PriorityQueue):
Can contain up to V nodes in the worst case.
→ O(V)

Adding everything together:
O(V + E) + O(V) + O(V) + O(V) = O(V + E)

Floyd-Warshall

class FloydWarshall {
  public void floydWarshall(int[][] graph) {
    int V = graph.length;
    int[][] dist = new int[V][V];

    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        dist[i][j] = Integer.MAX_VALUE;
      }
    }

    for (int k = 0; k < V; k++) {
      for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
          if (dist[i][k] < Integer.MAX_VALUE && dist[k][j] < Integer.MAX_VALUE) {
              dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
          }
        }
      }
    }
  }
}

Time Complexity: O(V^3)

Space Complexity: O(V^2)