Stone-r1 · Stone-r1 · Aug 4, 2025 · Aug 4, 2025 · Aug 4, 2025 · Aug 4, 2025
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -13,6 +13,7 @@ set(SOURCES
     src/algorithms/bfs.cpp
     src/algorithms/dfs.cpp
     src/algorithms/dijkstra.cpp
+    src/algorithms/bellmanFord.cpp
 )
 
 add_executable(${PROJECT_NAME} ${SOURCES})

diff --git a/src/algorithms/bellmanFord.cpp b/src/algorithms/bellmanFord.cpp
@@ -0,0 +1,92 @@
+#include "bellmanFord.h"
+const long long MAX_VALUE = 1e18;
+
+BellmanFord::BellmanFord(const vector<vector<pair<int, int>>>& adj, int startNode) : 
+    graph(adj),
+    distances(adj.size(), MAX_VALUE),
+    finished(false),
+    start(startNode)
+{
+    vertices = graph.size();
+    distances[startNode] = 0;
+    history.push_back({startNode, startNode, 0});
+
+    // flatten edges
+    for (int node = 0; node < vertices; node++) {
+        for (const auto& [neighbor, weight] : graph[node]) {
+            edges.emplace_back(node, neighbor, weight);
+        }
+    }
+}
+
+Step BellmanFord::stepForward() {  
+    if (currentStepIndex + 1 < history.size()) {
+        return history[++currentStepIndex];
+    }
+
+    if (currentPhase >= vertices - 1) {
+        finished = true;
+        return {-1, -1, -1};
+    }
+
+    if (finished) {
+        return {-1, -1, -1};
+    } 
+
+    auto [node, neighbor, weight] = edges[currentEdgeIndex];
+    bool relaxed = false;
+    if (distances[node] != MAX_VALUE && distances[node] + weight < distances[neighbor]) {
+        distances[neighbor] = distances[node] + weight;
+        relaxed = true;
+    }
+
+    if (++currentEdgeIndex >= edges.size()) {
+        currentEdgeIndex = 0;
+        currentPhase++;
+    }
+
+    if (currentPhase >= vertices - 1) {
+        finished = true;
+    }
+
+    if (relaxed) { 
+        Step step = Step({node, neighbor, distances[neighbor]});
+        history.push_back(step);
+        currentStepIndex++;
+        return step;
+    } else {
+        return stepForward();
+    }
+}
+
+Step BellmanFord::stepBackward() {
+    if (currentStepIndex <= 0) {
+        return {-1, -1, -1};
+    }
+
+    return history[--currentStepIndex];
+}
+
+bool BellmanFord::isFinished() const {
+    return finished && currentStepIndex + 1 >= history.size();
+}
+
+int BellmanFord::getCurrentStepIndex() const {
+    return currentStepIndex;
+}
+
+int BellmanFord::getTotalSteps() const {
+    return history.size();
+}
+
+Step BellmanFord::getHistory(int index) const {
+    return history[index];
+}
+
+int BellmanFord::getStartNode() const {
+    return start;
+}
+
+int BellmanFord::getCumulativeDistance(int nodeIndex) const {
+    return distances[nodeIndex];
+}
diff --git a/src/algorithms/bellmanFord.h b/src/algorithms/bellmanFord.h
@@ -0,0 +1,39 @@
+#ifndef BELLMANFORD_H
+#define BELLMANFORD_H
+
+#include "traversalAlgorithm.h"
+#include <vector>
+#include <tuple>
+
+using std::vector;
+using std::pair;
+
+class BellmanFord : public TraversalAlgorithm {
+private:
+    const vector<vector<pair<int, int>>>& graph;
+    vector<std::tuple<int, int, int>> edges;
+    vector<long long> distances;
+    bool finished;
+    vector<Step> history;
+
+    int currentStepIndex = -1;
+    int start;
+    int vertices;
+    int currentPhase;
+    int currentEdgeIndex;
+
+public:
+    BellmanFord(const vector<vector<pair<int, int>>>& adj, int startNode);
+
+    Step stepForward();
+    Step stepBackward();
+
+    bool isFinished() const;
+    int getCurrentStepIndex() const;
+    int getTotalSteps() const;
+    Step getHistory(int index) const;
+    int getStartNode() const;
+    int getCumulativeDistance(int nodeIndex) const;
+};
+
+#endif
diff --git a/src/board.cpp b/src/board.cpp
@@ -157,6 +157,7 @@ void Board::drawNodes() {
         }
 
         DrawCircle(nodePosition.x, nodePosition.y, node.getNodeRadius(), color);
+        DrawRing(nodePosition, node.getNodeRadius() - node.getNodeRadius() / 8, node.getNodeRadius(), 0.0f, 360.0f, 100, BLACK);
     }  
 }
 
@@ -170,7 +171,8 @@ void Board::drawEdges() {
             if (!neighbor->isNodeValid()) continue;
 
             Color color = highlightedEdges.count({node.getNodeIndex(), neighbor->getNodeIndex()}) ? DARKBLUE : GREEN;
-            DrawLineEx(node.getNodePosition(), neighbor->getNodePosition(), 5.0f, color);
+            DrawLineEx(node.getNodePosition(), neighbor->getNodePosition(), 6.0f, color);
+            // DrawLineEx(node.getNodePosition(), neighbor->getNodePosition(), 2.0f, color);
         }
     }         
 }
@@ -283,6 +285,21 @@ void Board::runDijkstra(const Vector2& startNodePosition) {
     }
 }
 
+void Board::runBellmanFord(const Vector2& startNodePosition) {
+    if (!isGraphWeighted()) {
+        std::cout << "Graph must be weighted to run dijkstra\n";
+        return;
+    }
+
+    Node* startNode = findNodeFromPosition(startNodePosition);
+    if (startNode) {
+        resetRunning();
+        startNodeIndex = -1;
+        currentAlgo = std::make_unique<BellmanFord>(graph, startNode->getNodeIndex());
+        isRunning = true;
+    }
+}
+
 void Board::highlightNode(const int& index) {
     if (index >= 0 && index < nodes.size() && nodes[index].isNodeValid()) {
         nodes[index].setHighlight();

diff --git a/src/board.h b/src/board.h
@@ -9,6 +9,7 @@
 #include "algorithms/bfs.h"
 #include "algorithms/dfs.h"
 #include "algorithms/dijkstra.h"
+#include "algorithms/bellmanFord.h"
 using std::vector;
 
 
@@ -54,6 +55,7 @@ class Board {
     void runBFS(const Vector2& startNodePosition);
     void runDFS(const Vector2& startNodePosition);
     void runDijkstra(const Vector2& startNodePosition);
+    void runBellmanFord(const Vector2& startNodePosition);
 
     void stepForward();
     void stepBackward();

diff --git a/src/main.cpp b/src/main.cpp
@@ -67,6 +67,12 @@ void handleLeftClick(Board& board, Sidebar& sidebar, Vector2 mouse) {
             return;
         }
 
+        if (sidebar.isButtonClicked("Bellman-Ford")) {
+            board.runBellmanFord(startNode);
+            sidebar.resetClicks();
+            return;
+        }
+
         if (sidebar.isButtonClicked("Weighted")) {
             if (!board.isGraphEmpty()) {
                 return; // can't flip the graph weight if edges were added.
@@ -171,3 +177,4 @@ int main() {
 
     CloseWindow();
 }
+