Floyd-Warshall in Python, Java and TypeScript

import math


def floyd_warshall(vertices, edges):
    distance = {i: {j: 0 if i == j else math.inf for j in vertices} for i in vertices}
    next_hop = {i: {j: j if i == j else None for j in vertices} for i in vertices}
    for u, v, weight in edges:
        distance[u][v] = weight
        next_hop[u][v] = v
    for k in vertices:
        for i in vertices:
            for j in vertices:
                if distance[i][k] + distance[k][j] < distance[i][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
                    next_hop[i][j] = next_hop[i][k]
    return distance, next_hop


def path(next_hop, start, end):
    if next_hop[start][end] is None:
        return []
    route = [start]
    while start != end:
        start = next_hop[start][end]
        route.append(start)
    return route


VERTICES = ["A", "B", "C", "D", "E"]
EDGES = [("A", "B", 2), ("A", "C", 7), ("B", "C", 3), ("B", "D", 8), ("C", "D", 2), ("C", "E", 6), ("D", "E", 1)]

distance, next_hop = floyd_warshall(VERTICES, EDGES)
print(" " + "".join(f"{v:>3}" for v in VERTICES))
for i in VERTICES:
    print(i + "".join(f"{'-' if distance[i][j] == math.inf else distance[i][j]:>3}" for j in VERTICES))
print("path A to E:", " -> ".join(path(next_hop, "A", "E")))

import java.util.ArrayList;
import java.util.List;

public class FloydCode {
    static final int INF = Integer.MAX_VALUE;

    record Result(int[][] distance, int[][] nextHop) {}

    static Result floydWarshall(int n, int[][] edges) {
        int[][] distance = new int[n][n];
        int[][] nextHop = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                distance[i][j] = i == j ? 0 : INF;
                nextHop[i][j] = i == j ? j : -1;
            }
        }
        for (int[] edge : edges) {
            distance[edge[0]][edge[1]] = edge[2];
            nextHop[edge[0]][edge[1]] = edge[1];
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (distance[i][k] != INF && distance[k][j] != INF && distance[i][k] + distance[k][j] < distance[i][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                        nextHop[i][j] = nextHop[i][k];
                    }
                }
            }
        }
        return new Result(distance, nextHop);
    }

    static List<Integer> path(int[][] nextHop, int start, int end) {
        List<Integer> route = new ArrayList<>();
        if (nextHop[start][end] == -1) return route;
        route.add(start);
        while (start != end) {
            start = nextHop[start][end];
            route.add(start);
        }
        return route;
    }

    public static void main(String[] args) {
        String[] names = {"A", "B", "C", "D", "E"};
        int[][] edges = {{0, 1, 2}, {0, 2, 7}, {1, 2, 3}, {1, 3, 8}, {2, 3, 2}, {2, 4, 6}, {3, 4, 1}};
        Result result = floydWarshall(names.length, edges);
        StringBuilder header = new StringBuilder(" ");
        for (String name : names) header.append(String.format("%3s", name));
        System.out.println(header);
        for (int i = 0; i < names.length; i++) {
            StringBuilder row = new StringBuilder(names[i]);
            for (int j = 0; j < names.length; j++) {
                int value = result.distance()[i][j];
                row.append(String.format("%3s", value == INF ? "-" : String.valueOf(value)));
            }
            System.out.println(row);
        }
        List<String> route = new ArrayList<>();
        for (int vertex : path(result.nextHop(), 0, 4)) route.add(names[vertex]);
        System.out.println("path A to E: " + String.join(" -> ", route));
    }
}

type Edge = [string, string, number];

function floydWarshall(vertices: string[], edges: Edge[]): { distance: Map<string, Map<string, number>>; nextHop: Map<string, Map<string, string | null>> } {
  const distance = new Map(vertices.map((i) => [i, new Map(vertices.map((j) => [j, i === j ? 0 : Infinity]))]));
  const nextHop = new Map(vertices.map((i) => [i, new Map<string, string | null>(vertices.map((j) => [j, i === j ? j : null]))]));
  for (const [u, v, weight] of edges) {
    distance.get(u)!.set(v, weight);
    nextHop.get(u)!.set(v, v);
  }
  for (const k of vertices) {
    for (const i of vertices) {
      for (const j of vertices) {
        const through = distance.get(i)!.get(k)! + distance.get(k)!.get(j)!;
        if (through < distance.get(i)!.get(j)!) {
          distance.get(i)!.set(j, through);
          nextHop.get(i)!.set(j, nextHop.get(i)!.get(k)!);
        }
      }
    }
  }
  return { distance, nextHop };
}

function path(nextHop: Map<string, Map<string, string | null>>, start: string, end: string): string[] {
  if (nextHop.get(start)!.get(end) === null) return [];
  const route = [start];
  while (start !== end) {
    start = nextHop.get(start)!.get(end)!;
    route.push(start);
  }
  return route;
}

const vertices = ["A", "B", "C", "D", "E"];
const edges: Edge[] = [["A", "B", 2], ["A", "C", 7], ["B", "C", 3], ["B", "D", 8], ["C", "D", 2], ["C", "E", 6], ["D", "E", 1]];
const { distance, nextHop } = floydWarshall(vertices, edges);
const cell = (value: number): string => (value === Infinity ? "-" : String(value)).padStart(3);
console.log(" " + vertices.map((v) => v.padStart(3)).join(""));
for (const i of vertices) console.log(i + vertices.map((j) => cell(distance.get(i)!.get(j)!)).join(""));
console.log(`path A to E: ${path(nextHop, "A", "E").join(" -> ")}`);