cpp/graph/warshall_floyd.hpp

• View this file on GitHub
• Last update: 2024-10-29 23:42:15+09:00
• Include: #include "cpp/graph/warshall_floyd.hpp"
• Link: https://algo-logic.info/warshall-floyd/

Depends on

• cpp/graph/graph_matrix.hpp
• 共通ヘッダー (cpp/template/small_template.hpp)

Verified with

• cpp/verify/warshall_floyd.test.cpp

Code

#pragma once
#include "graph/graph_matrix.hpp"
#include "template/small_template.hpp"

/**
 * ワーシャルフロイド法
 * 有向グラフの全点対最短経路 O(V^3)
 * 到達不能：max
 * https://algo-logic.info/warshall-floyd/
 */
template <class Cost> void MatrixGraph<Cost>::warshall_floyd() {
  if (shortest_path_dist.size()) {
    return;
  }
  shortest_path_dist = mat;
  shortest_path_parent = vector<vector<int>>(n, vector<int>(n, -1));
  for (int i = 0; i < n; ++i) {
    shortest_path_parent[i][i] = i;
  }
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (shortest_path_dist[i][k] + shortest_path_dist[k][j] <
            shortest_path_dist[i][j]) {
          shortest_path_dist[i][j] =
              shortest_path_dist[i][k] + shortest_path_dist[k][j];
          shortest_path_parent[i][j] = shortest_path_parent[k][j];
        }
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (shortest_path_dist[i][j] > MatrixGraph<Cost>::UNREACHABLE / 2) {
        shortest_path_dist[i][j] = MatrixGraph<Cost>::UNREACHABLE;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    if (shortest_path_dist[i][i] < 0) {
      negative_cycle = true;
      break;
    }
  }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: graph/graph_matrix.hpp: line -1: no such header

Back to top page