Mercurial > lbo > hg > ccplay
changeset 24:b89680a8af68 default tip
graph: detect negative cycles
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 09 Apr 2023 17:27:20 +0200 |
parents | c3fb5f666e2d |
children | |
files | graph.cc |
diffstat | 1 files changed, 12 insertions(+), 4 deletions(-) [+] |
line wrap: on
line diff
--- a/graph.cc Sun Apr 09 17:17:04 2023 +0200 +++ b/graph.cc Sun Apr 09 17:27:20 2023 +0200 @@ -96,9 +96,13 @@ if (cost[a] + adj[a,b] < cost[b]) cost[b] = cost[a] + adj[a, b]; } + if (adj[a,a] < 0) { + fmt::print("negative cycle found for {}\n", a); + goto outer; + } } } - +outer: fmt::print("{}\n", cost); } @@ -135,15 +139,19 @@ if (adj[i,j] + adj[j,k] < adj[i,k]) adj[i,k] = adj[i,j]+adj[j,k]; } } + if (adj[i,i] < 0) { + fmt::print("Negative cycle found for {}\n", i); + goto outer; + } } } - +outer: fmt::print("\n"); adj.print(); } int main(void) { - timeit_f([]() { bellman_ford(); }, "bellman-ford"); - floyd_warshall(); + timeit_f(bellman_ford, "bellman-ford"); + timeit_f(floyd_warshall, "floyd-warshall"); return 0; }