• shortest path between all pairs of vertices, negative edges allowed
    • nope - negative cycles
  • dist matrix
    • 2 차원 거리 배열
  • predecessor matrix
    • 2 차원 방문점 배열
  •   void floydWarshall(vector<vector<int>> &dist) {
          int V = dist.size();
          
          // Add all vertices one by one to
          // the set of intermediate vertices.
          for (int k = 0; k < V; k++) {
          
              // Pick all vertices as source one by one
              for (int i = 0; i < V; i++) {
      
                  // Pick all vertices as destination
                  // for the above picked source
                  for (int j = 0; j < V; j++) {
      
                      // shortest path from
                      // i to j 
                      if(dist[i][k] != 1e8 && dist[k][j]!= 1e8)
      	                dist[i][j] = min(
      						dist[i][j],
      						dist[i][k] + dist[k][j]
      					);
                  }
              }
          }
      	for (int i = 0; i < V; ++i) {
      	    if (dist[i][i] < 0) {
      	        // i 정점에서 시작하는 음수 사이클 존재
      	    }
      	}
      }