floyd-warshall algorithm

<2023-05-12 Fri 02:01:26>
cs
an algorithm to find the distance matrix of a directed weighted graph
let be a weighted graph with the set of vertices
  1. we denote by the induced subgraph by the vertices
  2. for every pair of vertices we denote by the induced subgraph by the vertices
  3. for every pair of vertices, we denote by one of the minimal paths (if it exists) from to in
for every pair of vertices
  1. if in there exists a minimal path from to , , we write
    • if in \(G^{(k)}_{ij}\) there exists a path from \(i\) to \(j\) that contains a negative cycle we write \(d^{(k)}_{ij} = -\infty\)
    • if in \(G^{(k)}_{ij}\) there isnt a path from \(i\) to \(j\) we write \(d^{(k)}_{ij} = \infty\)
  2. for every if in there isnt a negative cycle that touches then
  3. for every if in there is a negative cycle that touches then
  1. for every , (if it exists) is the shortest path from to without any vertices in between, meaning the path is just the edge
  2. for every , (if it exists) is the shortest path from to , i.e.
  3. and , otherwise
  4. if the directed edges are defined in , then
the time complexity of the algorithm is