Tweeted twitter.com/StackCodeReview/status/1234584537109319680

occurred Mar 2, 2020 at 21:01

Noticed an error in the code

Source Link

edited Mar 1, 2020 at 14:43

63
7

EDIT: I noticed I should've added a field that shows whether a node is open or not, in order to eliminate pushing the same node twice to the priority queue.

added comments for not correctly named variables functionalities

Source Link

edited Feb 29, 2020 at 23:54

Balog Szilárd

63
7

#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <climits>

using namespace std;

class Node {
    int label;
    int d;                    // Overall distance from the start point
    bool processed;           // Visited node indicator
    Node* parent;
    vector<Node*> neighbors;  
    vector<int> dist;         // Distance from each heighbor

public:
    Node(int = 0);
    void addNeighbor(Node*);
    void addDist(int);
    void setLabel(int);
    void setD(int);
    void setProccessed(bool);
    void setParent(Node*);
    int getLabel();
    int getD();
    bool isProcessed();
    Node* getParent();
    vector<Node *> getNeighbors();
    vector<int> getDist();
};

Node::Node(int label) {
    this->label = label;
}

void Node::addNeighbor(Node* neighbor) {
    neighbors.push_back(neighbor);
}

void Node::addDist(int d) {
    dist.push_back(d);
}

void Node::setLabel(int label) {
    this->label = label;
}

void Node::setD(int d) {
    this->d = d;
}

void Node::setParent(Node* node) {
    parent = node;
}

void Node::setProccessed(bool p) {
    processed = p;
}

int Node::getLabel() {
    return label;
}

int Node::getD() {
    return d;
}

Node* Node::getParent() {
    return parent;
}

bool Node::isProcessed() {
    return processed;
}

vector<Node*> Node::getNeighbors() {
    return neighbors;
}

vector<int> Node::getDist() {
    return dist;
}

void init(ifstream& f, Node**& nodes, int& n) {
    f >> n;
    
    nodes = new Node*[n];

    int** adj = new int*[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new int[n];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adj[i][j] = 0;
        }
    }

    int label, start, end, weight;
    while(f >> start >> end >> weight) {
        adj[start - 1][end - 1] = weight;
        adj[end - 1][start - 1] = weight;
    }

    for (int i = 0; i < n; i++) {
        nodes[i] = new Node(i + 1);
    }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (adj[i][j] != 0)
                {
                    nodes[i]->addNeighbor(nodes[j]);
                    nodes[i]->addDist(adj[i][j]);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            delete[] adj[i];
        }
        delete[] adj;
}

void initNodes(Node** nodes, int n) {
    for (int i = 0; i < n; i++) {
        nodes[i]->setD(INT_MAX);
        nodes[i]->setParent(NULL);
        nodes[i]->setProccessed(false);
    }
}

class Compare {
public:
    bool operator()(Node* n1, Node* n2) {
        return n1->getD() > n2->getD();
    }
};

void writePath(Node* node) {
    if (node) {
        int label = node->getLabel();
        node = node->getParent();
        writePath(node);
        if(node) {
            cout << " -> ";
        }
        cout << label;
    }
}

void dijkstra(Node** nodes, int n) {
    cout << "Dijkstra algorithm" << endl;

    int start = 1;
    int end = 7;

    initNodes(nodes, n);

    nodes[start - 1]->setD(0);

    priority_queue<Node*, vector<Node*>, Compare> queue;
    queue.push(nodes[start - 1]);
    Node* current;
    
    do {
        current = queue.top();
        queue.pop();
        current->setProccessed(true);

        vector<Node *> neighbors = current->getNeighbors();
        for (unsigned int i = 0; i < neighbors.size(); i++) {
            if((!neighbors.at(i)->isProcessed())) {
                if((neighbors.at(i)->getD() == INT_MAX || (current->getD() + current->getDist().at(i) < neighbors.at(i)->getD()))) {
                    neighbors.at(i)->setParent(current);
                    neighbors.at(i)->setD(current->getD() + current->getDist().at(i));
                }
                queue.push(neighbors.at(i));
            }
        }
    } while(current->getLabel() != end);
    /*
    */
    writePath(current);
    cout << endl;
}

int main() {

    ifstream f("input.in");

    int numOfNodes;
    Node** nodes;

    init(f, nodes, numOfNodes);

    for (int i = 0; i < numOfNodes; i++) {
        vector<Node *> neighbors = nodes[i]->getNeighbors();
        cout << i + 1 << ": ";
        for (int j = 0; j < neighbors.size(); j++) {
            cout << neighbors[j]->getLabel() << " ";
        }
        cout << endl;
    }
    cout << endl;

    dijkstra(nodes, numOfNodes);

    for (int i = 0; i < numOfNodes; i++) {
        delete nodes[i];
    }
    delete[] nodes;

    return 0;
}

#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <climits>

using namespace std;

class Node {
    int label;
    int d;
    bool processed;
    Node* parent;
    vector<Node*> neighbors;
    vector<int> dist;

public:
    Node(int = 0);
    void addNeighbor(Node*);
    void addDist(int);
    void setLabel(int);
    void setD(int);
    void setProccessed(bool);
    void setParent(Node*);
    int getLabel();
    int getD();
    bool isProcessed();
    Node* getParent();
    vector<Node *> getNeighbors();
    vector<int> getDist();
};

Node::Node(int label) {
    this->label = label;
}

void Node::addNeighbor(Node* neighbor) {
    neighbors.push_back(neighbor);
}

void Node::addDist(int d) {
    dist.push_back(d);
}

void Node::setLabel(int label) {
    this->label = label;
}

void Node::setD(int d) {
    this->d = d;
}

void Node::setParent(Node* node) {
    parent = node;
}

void Node::setProccessed(bool p) {
    processed = p;
}

int Node::getLabel() {
    return label;
}

int Node::getD() {
    return d;
}

Node* Node::getParent() {
    return parent;
}

bool Node::isProcessed() {
    return processed;
}

vector<Node*> Node::getNeighbors() {
    return neighbors;
}

vector<int> Node::getDist() {
    return dist;
}

void init(ifstream& f, Node**& nodes, int& n) {
    f >> n;
    
    nodes = new Node*[n];

    int** adj = new int*[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new int[n];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adj[i][j] = 0;
        }
    }

    int label, start, end, weight;
    while(f >> start >> end >> weight) {
        adj[start - 1][end - 1] = weight;
        adj[end - 1][start - 1] = weight;
    }

    for (int i = 0; i < n; i++) {
        nodes[i] = new Node(i + 1);
    }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (adj[i][j] != 0)
                {
                    nodes[i]->addNeighbor(nodes[j]);
                    nodes[i]->addDist(adj[i][j]);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            delete[] adj[i];
        }
        delete[] adj;
}

void initNodes(Node** nodes, int n) {
    for (int i = 0; i < n; i++) {
        nodes[i]->setD(INT_MAX);
        nodes[i]->setParent(NULL);
        nodes[i]->setProccessed(false);
    }
}

class Compare {
public:
    bool operator()(Node* n1, Node* n2) {
        return n1->getD() > n2->getD();
    }
};

void writePath(Node* node) {
    if (node) {
        int label = node->getLabel();
        node = node->getParent();
        writePath(node);
        if(node) {
            cout << " -> ";
        }
        cout << label;
    }
}

void dijkstra(Node** nodes, int n) {
    cout << "Dijkstra algorithm" << endl;

    int start = 1;
    int end = 7;

    initNodes(nodes, n);

    nodes[start - 1]->setD(0);

    priority_queue<Node*, vector<Node*>, Compare> queue;
    queue.push(nodes[start - 1]);
    Node* current;
    
    do {
        current = queue.top();
        queue.pop();
        current->setProccessed(true);

        vector<Node *> neighbors = current->getNeighbors();
        for (unsigned int i = 0; i < neighbors.size(); i++) {
            if((!neighbors.at(i)->isProcessed())) {
                if((neighbors.at(i)->getD() == INT_MAX || (current->getD() + current->getDist().at(i) < neighbors.at(i)->getD()))) {
                    neighbors.at(i)->setParent(current);
                    neighbors.at(i)->setD(current->getD() + current->getDist().at(i));
                }
                queue.push(neighbors.at(i));
            }
        }
    } while(current->getLabel() != end);
    /*
    */
    writePath(current);
    cout << endl;
}

int main() {

    ifstream f("input.in");

    int numOfNodes;
    Node** nodes;

    init(f, nodes, numOfNodes);

    for (int i = 0; i < numOfNodes; i++) {
        vector<Node *> neighbors = nodes[i]->getNeighbors();
        cout << i + 1 << ": ";
        for (int j = 0; j < neighbors.size(); j++) {
            cout << neighbors[j]->getLabel() << " ";
        }
        cout << endl;
    }
    cout << endl;

    dijkstra(nodes, numOfNodes);

    for (int i = 0; i < numOfNodes; i++) {
        delete nodes[i];
    }
    delete[] nodes;

    return 0;
}

#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <climits>

using namespace std;

class Node {
    int label;
    int d;                    // Overall distance from the start point
    bool processed;           // Visited node indicator
    Node* parent;
    vector<Node*> neighbors;  
    vector<int> dist;         // Distance from each heighbor

public:
    Node(int = 0);
    void addNeighbor(Node*);
    void addDist(int);
    void setLabel(int);
    void setD(int);
    void setProccessed(bool);
    void setParent(Node*);
    int getLabel();
    int getD();
    bool isProcessed();
    Node* getParent();
    vector<Node *> getNeighbors();
    vector<int> getDist();
};

Node::Node(int label) {
    this->label = label;
}

void Node::addNeighbor(Node* neighbor) {
    neighbors.push_back(neighbor);
}

void Node::addDist(int d) {
    dist.push_back(d);
}

void Node::setLabel(int label) {
    this->label = label;
}

void Node::setD(int d) {
    this->d = d;
}

void Node::setParent(Node* node) {
    parent = node;
}

void Node::setProccessed(bool p) {
    processed = p;
}

int Node::getLabel() {
    return label;
}

int Node::getD() {
    return d;
}

Node* Node::getParent() {
    return parent;
}

bool Node::isProcessed() {
    return processed;
}

vector<Node*> Node::getNeighbors() {
    return neighbors;
}

vector<int> Node::getDist() {
    return dist;
}

void init(ifstream& f, Node**& nodes, int& n) {
    f >> n;
    
    nodes = new Node*[n];

    int** adj = new int*[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new int[n];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adj[i][j] = 0;
        }
    }

    int label, start, end, weight;
    while(f >> start >> end >> weight) {
        adj[start - 1][end - 1] = weight;
        adj[end - 1][start - 1] = weight;
    }

    for (int i = 0; i < n; i++) {
        nodes[i] = new Node(i + 1);
    }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (adj[i][j] != 0)
                {
                    nodes[i]->addNeighbor(nodes[j]);
                    nodes[i]->addDist(adj[i][j]);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            delete[] adj[i];
        }
        delete[] adj;
}

void initNodes(Node** nodes, int n) {
    for (int i = 0; i < n; i++) {
        nodes[i]->setD(INT_MAX);
        nodes[i]->setParent(NULL);
        nodes[i]->setProccessed(false);
    }
}

class Compare {
public:
    bool operator()(Node* n1, Node* n2) {
        return n1->getD() > n2->getD();
    }
};

void writePath(Node* node) {
    if (node) {
        int label = node->getLabel();
        node = node->getParent();
        writePath(node);
        if(node) {
            cout << " -> ";
        }
        cout << label;
    }
}

void dijkstra(Node** nodes, int n) {
    cout << "Dijkstra algorithm" << endl;

    int start = 1;
    int end = 7;

    initNodes(nodes, n);

    nodes[start - 1]->setD(0);

    priority_queue<Node*, vector<Node*>, Compare> queue;
    queue.push(nodes[start - 1]);
    Node* current;
    
    do {
        current = queue.top();
        queue.pop();
        current->setProccessed(true);

        vector<Node *> neighbors = current->getNeighbors();
        for (unsigned int i = 0; i < neighbors.size(); i++) {
            if((!neighbors.at(i)->isProcessed())) {
                if((neighbors.at(i)->getD() == INT_MAX || (current->getD() + current->getDist().at(i) < neighbors.at(i)->getD()))) {
                    neighbors.at(i)->setParent(current);
                    neighbors.at(i)->setD(current->getD() + current->getDist().at(i));
                }
                queue.push(neighbors.at(i));
            }
        }
    } while(current->getLabel() != end);
    /*
    */
    writePath(current);
    cout << endl;
}

int main() {

    ifstream f("input.in");

    int numOfNodes;
    Node** nodes;

    init(f, nodes, numOfNodes);

    for (int i = 0; i < numOfNodes; i++) {
        vector<Node *> neighbors = nodes[i]->getNeighbors();
        cout << i + 1 << ": ";
        for (int j = 0; j < neighbors.size(); j++) {
            cout << neighbors[j]->getLabel() << " ";
        }
        cout << endl;
    }
    cout << endl;

    dijkstra(nodes, numOfNodes);

    for (int i = 0; i < numOfNodes; i++) {
        delete nodes[i];
    }
    delete[] nodes;

    return 0;
}

Source Link

asked Feb 29, 2020 at 22:54

Balog Szilárd

63
7

Dijkstra Algorithm implementation in C++

I have implemented Dijkstra's algorithm in C++, but it seems a bit complicated since I really tried to follow the process of the algorithm as much as I could. If there's any simplification you would suggest, I would really appreciate, because this task was only for me to get familiarized with this method before the A* algorithm. The whole class thing about the nodes might be unnecesary, but I really like to think of these objects and to treat them like real things.

#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <climits>

using namespace std;

class Node {
    int label;
    int d;
    bool processed;
    Node* parent;
    vector<Node*> neighbors;
    vector<int> dist;

public:
    Node(int = 0);
    void addNeighbor(Node*);
    void addDist(int);
    void setLabel(int);
    void setD(int);
    void setProccessed(bool);
    void setParent(Node*);
    int getLabel();
    int getD();
    bool isProcessed();
    Node* getParent();
    vector<Node *> getNeighbors();
    vector<int> getDist();
};

Node::Node(int label) {
    this->label = label;
}

void Node::addNeighbor(Node* neighbor) {
    neighbors.push_back(neighbor);
}

void Node::addDist(int d) {
    dist.push_back(d);
}

void Node::setLabel(int label) {
    this->label = label;
}

void Node::setD(int d) {
    this->d = d;
}

void Node::setParent(Node* node) {
    parent = node;
}

void Node::setProccessed(bool p) {
    processed = p;
}

int Node::getLabel() {
    return label;
}

int Node::getD() {
    return d;
}

Node* Node::getParent() {
    return parent;
}

bool Node::isProcessed() {
    return processed;
}

vector<Node*> Node::getNeighbors() {
    return neighbors;
}

vector<int> Node::getDist() {
    return dist;
}

void init(ifstream& f, Node**& nodes, int& n) {
    f >> n;
    
    nodes = new Node*[n];

    int** adj = new int*[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new int[n];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adj[i][j] = 0;
        }
    }

    int label, start, end, weight;
    while(f >> start >> end >> weight) {
        adj[start - 1][end - 1] = weight;
        adj[end - 1][start - 1] = weight;
    }

    for (int i = 0; i < n; i++) {
        nodes[i] = new Node(i + 1);
    }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (adj[i][j] != 0)
                {
                    nodes[i]->addNeighbor(nodes[j]);
                    nodes[i]->addDist(adj[i][j]);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            delete[] adj[i];
        }
        delete[] adj;
}

void initNodes(Node** nodes, int n) {
    for (int i = 0; i < n; i++) {
        nodes[i]->setD(INT_MAX);
        nodes[i]->setParent(NULL);
        nodes[i]->setProccessed(false);
    }
}

class Compare {
public:
    bool operator()(Node* n1, Node* n2) {
        return n1->getD() > n2->getD();
    }
};

void writePath(Node* node) {
    if (node) {
        int label = node->getLabel();
        node = node->getParent();
        writePath(node);
        if(node) {
            cout << " -> ";
        }
        cout << label;
    }
}

void dijkstra(Node** nodes, int n) {
    cout << "Dijkstra algorithm" << endl;

    int start = 1;
    int end = 7;

    initNodes(nodes, n);

    nodes[start - 1]->setD(0);

    priority_queue<Node*, vector<Node*>, Compare> queue;
    queue.push(nodes[start - 1]);
    Node* current;
    
    do {
        current = queue.top();
        queue.pop();
        current->setProccessed(true);

        vector<Node *> neighbors = current->getNeighbors();
        for (unsigned int i = 0; i < neighbors.size(); i++) {
            if((!neighbors.at(i)->isProcessed())) {
                if((neighbors.at(i)->getD() == INT_MAX || (current->getD() + current->getDist().at(i) < neighbors.at(i)->getD()))) {
                    neighbors.at(i)->setParent(current);
                    neighbors.at(i)->setD(current->getD() + current->getDist().at(i));
                }
                queue.push(neighbors.at(i));
            }
        }
    } while(current->getLabel() != end);
    /*
    */
    writePath(current);
    cout << endl;
}

int main() {

    ifstream f("input.in");

    int numOfNodes;
    Node** nodes;

    init(f, nodes, numOfNodes);

    for (int i = 0; i < numOfNodes; i++) {
        vector<Node *> neighbors = nodes[i]->getNeighbors();
        cout << i + 1 << ": ";
        for (int j = 0; j < neighbors.size(); j++) {
            cout << neighbors[j]->getLabel() << " ";
        }
        cout << endl;
    }
    cout << endl;

    dijkstra(nodes, numOfNodes);

    for (int i = 0; i < numOfNodes; i++) {
        delete nodes[i];
    }
    delete[] nodes;

    return 0;
}

INPUT:

c++algorithm pathfinding

Stack Exchange Network

Return to Question

Dijkstra Algorithm implementation in C++