--- a/graph.cc	Sun Apr 09 12:07:14 2023 +0200
+++ b/graph.cc	Sun Apr 09 17:17:04 2023 +0200
@@ -2,6 +2,7 @@
 
 #include <iterator>
 #include <ranges>
+#include <tuple>
 #include <vector>
 
 using namespace std;
@@ -10,10 +11,11 @@
     requires random_access_iterator<Iter> && is_same_v<remove_cv_t<iter_value_t<Iter>>, remove_cv_t<T>>
 class MDSpan {
     const Iter begin, end;
-    const size_t Nx, Ny;
 
     public:
 
+    const size_t Nx, Ny;
+
     template<typename R>
         requires is_same_v<ranges::iterator_t<R>, Iter>
     MDSpan(R&& rng, size_t Nx, size_t Ny) : begin(std::begin(rng)), end(std::end(rng)), Nx(Nx), Ny(Ny) {
@@ -32,6 +34,15 @@
         size_t ix = y * Nx + x;
         return begin[ix];
     }
+
+    void print() {
+        for (size_t y = 0; y < Ny; y++) {
+            for (size_t x = 0; x < Nx; x++) {
+                fmt::print("{:5} ", (*this)[x, y]);
+            }
+            fmt::print("\n");
+        }
+    }
 };
 
 template<typename Cont> requires ranges::range<Cont>
@@ -57,18 +68,82 @@
 
 // https://www.techiedelight.com/single-source-shortest-paths-bellman-ford-algorithm/
 void bellman_ford() {
-    const vector<int> v(42);
+    const size_t nodes = 5;
+    const int inf = numeric_limits<int>::max();
+    vector<int> v(nodes * nodes);
 
     //MDSpan<const int, vector<int>::const_iterator> mds = make_mdspan(v, 6, 7);
-    auto mds = make_const_mdspan(v, 6, 7);
+    auto adj = make_mdspan(v, nodes, nodes);
+
+    adj[0, 1] = -1;
+    adj[0, 2] = 4;
+    adj[1, 2] = 3;
+    adj[1, 3] = 2;
+    adj[3, 1] = 1;
+    adj[1, 4] = 2;
+    adj[4, 3] = -3;
+    adj[3, 2] = 5;
+
+    adj.print();
+    vector<int> cost(nodes, inf);
+    cost[0] = 0;
+
+    for (int i = 0; i < nodes-1; i++) {
+        for (size_t a = 0; a < nodes; a++) {
+            for (size_t b = 0; b < nodes; b++) {
+                // Not elegant. Need separate store for adjacency, basically.
+                if (a == b || adj[a, b] == 0) continue;
+
+                if (cost[a] + adj[a,b] < cost[b]) cost[b] = cost[a] + adj[a, b];
+            }
+        }
+    }
+
+    fmt::print("{}\n", cost);
+}
 
-    //mds[3, 3] = 47;
-    fmt::print("{}\n", mds[2,3]);
-    //fmt::print("{}\n", mds[3,3]);
+void floyd_warshall() {
+    const size_t nodes = 4;
+    const int inf = numeric_limits<int>::max();
+    vector<tuple<int, int, int>> edges{
+        {1, 0, 4},
+        {1, 2, 3},
+        {3, 1, -1},
+        {0, 2, -2},
+        {2, 3, 2},
+    };
+
+    vector<int> adj_v(nodes*nodes);
+    auto adj = make_mdspan(adj_v, nodes, nodes);
+
+    for (const auto& e : edges){
+        adj[get<0>(e), get<1>(e)] = get<2>(e);
+    }
+    for (size_t i = 0; i < nodes; i++) {
+        for (size_t j = 0; j < nodes; j++) {
+            if (i == j) adj[i,j] = 0;
+            else if (adj[i,j] == 0) adj[i,j] = inf;
+        }
+    }
+
+    adj.print();
+
+    for (size_t j = 0; j < nodes; j++) {
+        for (size_t i = 0; i < nodes; i++) {
+            for (size_t k = 0; k < nodes; k++) {
+                if (adj[i, j] != inf && adj[j, k] != inf) {
+                    if (adj[i,j] + adj[j,k] < adj[i,k]) adj[i,k] = adj[i,j]+adj[j,k];
+                }
+            }
+        }
+    }
+
+    fmt::print("\n");
+    adj.print();
 }
 
 int main(void) {
-    bellman_ford();
-
+    timeit_f([]() { bellman_ford(); }, "bellman-ford");
+    floyd_warshall();
     return 0;
 }