ds-in-cpp/SPFloyd.hh at main · sudonam/ds-in-cpp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <deque>

struct AdjMatrixEdgeWeightedDigraph {
  int V;
  std::deque<std::deque<int>> adj;
  AdjMatrixEdgeWeightedDigraph(int v)
      : V{v}, adj(v, std::deque<int>(v, 0xffff)) {}
};

struct Floyd {
  bool negativeCycle;
  std::deque<std::deque<int>> distTo;

  Floyd(const AdjMatrixEdgeWeightedDigraph &G)
      : negativeCycle{false}, distTo{G.adj} {
    int V = G.V;
    for (int v = 0; v < V; ++v) distTo[v][v] = 0;

    for (int i = 0; i < V; ++i) {
      for (int v = 0; v < V; ++v) {
        if (distTo[v][i] == 0xffff) continue;
        for (int w = 0; w < V; ++w) {
          if (distTo[i][w] == 0xffff) continue;
          if (distTo[v][w] > distTo[v][i] + distTo[i][w])
            distTo[v][w] = distTo[v][i] + distTo[i][w];
        }
        if (distTo[v][v] < 0) {
          negativeCycle = true;
          return;
        }
      }
    }
  }
};