shortest_path

Chen-Py · Chen-Py · commit 9e8b329b0cfc · 2025-11-18T08:50:30.000Z
diff --git a/dijkstra.cpp b/dijkstra.cpp
@@ -0,0 +1,109 @@
+// import visualization libraries {
+#include "algorithm-visualizer.h"
+// }
+
+#include <vector>
+#include <string>
+#include <limits>
+
+using json = nlohmann::json;
+
+// Tracers: graph, array1d (S) and log console
+GraphTracer tracer = GraphTracer().directed(false).weighted().layoutCircle();
+Array1DTracer tracerS = Array1DTracer("Distances");
+LogTracer logger = LogTracer("Console");
+
+int main() {
+    const int N = 5;
+    // generate random graph like JS example: Randomize.Graph({ N: 5, ratio: 1, directed: false, weighted: true })
+    std::vector<int> Gmat(N * N);
+    Randomize::Integer randWeight(1, 9);
+    Randomize::Graph<int> Ggen(N, 1.0, randWeight);
+    // do NOT chain these methods: they return by value, which would modify a temporary
+    // (so Ggen would keep its defaults). Call them separately to modify the original.
+    Ggen.directed(false);
+    Ggen.weighted(true);
+    Ggen.fill(Gmat.data());
+
+    // convert to 2D vector for tracer.set
+    std::vector<std::vector<int>> G2(N, std::vector<int>(N));
+    for (int i = 0; i < N; ++i) {
+        for (int j = 0; j < N; ++j) {
+            G2[i][j] = Gmat[i * N + j];
+        }
+    }
+
+    // initialize S (distance array) with INF
+    const int INF = std::numeric_limits<int>::max();
+    std::vector<int> S(N, INF);
+
+    // layout and initial set
+    Layout::setRoot(VerticalLayout({tracer, tracerS, logger}));
+    tracer.log(logger);
+    tracer.set(G2);
+
+    // prepare display array for tracerS: use strings for INF, numbers otherwise
+    std::vector<json> Sdisplay(N);
+    for (int i = 0; i < N; ++i) Sdisplay[i] = "INF";
+    tracerS.set(Sdisplay);
+    Tracer::delay();
+
+    // pick random start and end (s != e)
+    Randomize::Integer randNode(0, N - 1);
+    int s = randNode.create();
+    int e;
+    do { e = randNode.create(); } while (e == s);
+
+    logger.println(std::string("finding the shortest path from ") + std::to_string(s) + " to " + std::to_string(e));
+    Tracer::delay();
+
+    // Dijkstra
+    std::vector<bool> D(N, false);
+    S[s] = 0;
+    tracerS.patch(s, 0);
+    Tracer::delay();
+    tracerS.depatch(s);
+    tracerS.select(s);
+
+    int k = N;
+    while (k--) {
+        int minIndex = -1;
+        int minDistance = INF;
+        for (int i = 0; i < N; ++i) {
+            if (!D[i] && S[i] < minDistance) {
+                minDistance = S[i];
+                minIndex = i;
+            }
+        }
+        if (minDistance == INF) break;
+
+        D[minIndex] = true;
+        tracerS.select(minIndex);
+        tracer.visit(minIndex);
+        Tracer::delay();
+
+        for (int i = 0; i < N; ++i) {
+            if (G2[minIndex][i] && S[i] > S[minIndex] + G2[minIndex][i]) {
+                S[i] = S[minIndex] + G2[minIndex][i];
+                tracerS.patch(i, S[i]);
+                tracer.visit(i, minIndex, S[i]);
+                Tracer::delay();
+                tracerS.depatch(i);
+                tracer.leave(i, minIndex);
+                Tracer::delay();
+            }
+        }
+
+        tracer.leave(minIndex);
+        Tracer::delay();
+    }
+
+    if (S[e] == INF) {
+        logger.println(std::string("there is no path from ") + std::to_string(s) + " to " + std::to_string(e));
+    } else {
+        logger.println(std::string("the shortest path from ") + std::to_string(s) + " to " + std::to_string(e) + " is " + std::to_string(S[e]));
+    }
+
+    Tracer::delay();
+    return 0;
+}
diff --git a/out.exe b/out.exe
diff --git a/test.cpp b/test.cpp
@@ -0,0 +1,91 @@
+// import visualization libraries {
+#include "algorithm-visualizer.h"
+// }
+
+#include <vector>
+#include <string>
+#include <limits>
+
+using namespace std;
+
+int main() {
+    // define tracer variables
+    GraphTracer tracer = GraphTracer("Graph").weighted();
+    LogTracer logger = LogTracer("Console");
+    Layout::setRoot(VerticalLayout({tracer, logger}));
+    tracer.log(logger);
+
+    // create random weighted graph
+    const int N = 5;
+    const double ratio = 1.0; // fully connected
+    Randomize::Graph<int> rg(N, ratio);
+    rg.weighted(true);
+    vector<int> G(N * N);
+    rg.fill(G.data());
+
+    // convert adjacency matrix to json and set tracer
+    nlohmann::json jG = nlohmann::json::array();
+    for (int i = 0; i < N; i++) {
+        nlohmann::json row = nlohmann::json::array();
+        for (int j = 0; j < N; j++) {
+            row.push_back(G[i * N + j]);
+        }
+        jG.push_back(row);
+    }
+    tracer.set(jG);
+    Tracer::delay();
+
+    // Floyd--Warshall
+    const double MAX_VALUE = numeric_limits<double>::infinity();
+    vector<vector<double>> S(N, vector<double>(N));
+    for (int i = 0; i < N; i++) {
+        for (int j = 0; j < N; j++) {
+            if (i == j) S[i][j] = 0;
+            else if (G[i * N + j] > 0) S[i][j] = G[i * N + j];
+            else S[i][j] = MAX_VALUE;
+        }
+    }
+
+    logger.println("finding the shortest paths from and to all nodes");
+
+    for (int k = 0; k < N; k++) {
+        for (int i = 0; i < N; i++) {
+            if (k == i) continue;
+            // visualize
+            tracer.visit(k, i);
+            Tracer::delay();
+            for (int j = 0; j < N; j++) {
+                if (i == j || j == k) continue;
+                // visualize
+                tracer.visit(j, k);
+                Tracer::delay();
+                if (S[i][j] > S[i][k] + S[k][j]) {
+                    // visualize
+                    tracer.visit(j, i, S[i][j]);
+                    Tracer::delay();
+                    S[i][j] = S[i][k] + S[k][j];
+                    // visualize
+                    tracer.leave(j, i, S[i][j]);
+                }
+                // visualize
+                tracer.leave(j, k);
+            }
+            // visualize
+            tracer.leave(k, i);
+            Tracer::delay();
+        }
+    }
+
+    // logger output
+    for (int i = 0; i < N; i++) {
+        for (int j = 0; j < N; j++) {
+            if (S[i][j] == MAX_VALUE) {
+                logger.println(string("there is no path from ") + to_string(i) + " to " + to_string(j));
+            } else {
+                logger.println(string("the shortest path from ") + to_string(i) + " to " + to_string(j) + " is " + to_string(S[i][j]));
+            }
+        }
+    }
+
+    return 0;
+}
