Dijkstra Algorithm implementation in C++

Overview

Dijkstra Algorithm my favorite algorithm :-)

I wrote an overview of how to do it StackOverflow:

My main observation is that you have crammed three things together that I would separate into three district code reviews (and thus three independent pieces of code). As a result I think your code is very tightly coupled where I think a loose coupling would be better design

1. I would separate the graph into its own class.
   Nodes/edges and their relationship should be completely independent to the algorithm.
   Yes there is a common shared interface but given a graph written by somebody else I could write a simple wrapper over the graph and still make it work with your algorithm.
2. You store the intermediate information about the traversal inside you node structure.
   I would separate this out into its own independent structure that is held separately to the graph.
   This can be customized what you want out of the algorithm (just best distance, or the route).
3. The algorithm should be independent of the graph and depend on a small interface.

The simplest interface:

NodeId       Graph::getNodeFromName(Name);
ListOFEdge   Graph::getOutputEdges(NodeId);
Edge         Is {Src(NodeId)/Dst(NodeId)/Cost(None negative value)}

This should be all you need.

Code Review

Please stop this:

using namespace std;

Read this article: Why is “using namespace std;” considered bad practice? My favorite answer is the second.

This should explain why using this can cause unexpected errors in all sorts of situation where you would not expect it.

In the class node:

class Node {

Data that is only relevant to a traversal algorithm. Its not relevant to the Node object and thus should not be here.

    int d;                    // Overall distance from the start point
    bool processed;           // Visited node indicator

A node in a graph has a parent?

    Node* parent;
    // OK. Having read all the way down to the algorithm I finally found it.
    //     You are recording the shortest path through the graph using this
    //     member.
    //     So I would add this to the members that belong to the algorithm
    //     rather than the node/graph. So some of the following comments
    //     about parents are out-dated by this final realization.
    //
    //     Better name for this member is defiantly needed.

These two members seem to be about the same thing. We are these in two different members?

    vector<Node*> neighbors;  
    vector<int>   dist;         // Distance from each heighbor

I would have combined them into single structure so that they always move around together.

    vector<std::pair<Node*, int>>  edge;  // destination and cost.

Wow this is an extensive interface for Node that does very little to help encapsulation. I would argue that this breaks encapsulation as you can simply modify anything without any control.

There is a default ID of zero to node?

    Node(int = 0);

So you can make lots of node's with ID of zero. I would definitely not make this a default value. I would go one step further and say that the user should not be setting the ID of the nodes (this is an internal property of the graph that is set internally).

The user may look up the ID of a node using a name but the user should not be able to set or alter the ID of node. It must be unique and therefore setting it is part of the graphs responcability.

Why can you add a neighbor and distance independently. This is just begging for bugs to happen. An edge has a destination and a cost.

    void addNeighbor(Node*);
    void addDist(int);

Now some graphs edge are bidirectional (others they are not). But when you have bidirectional edges the graph should provide a simpler interface that internally adds all the appropriate internal structures.

  // Adding a bi-directional edge.
  Graph::addEdge(Node& src, Node& dst, int cost) {
      src.addEdge(dst, cost);
      dst.addEdge(src, cost);
  }

Why are these modifiable externally?

    void setLabel(int);
    void setD(int);

Are these not set as part of the constructor to the node?

This is not part of a Node property but rather a property of the algorithm.

    void setProccessed(bool);
    bool isProcessed();

Why does a node have a parent.

    void setParent(Node*);
    Node* getParent();

Sure you can get the label/ID.

    int getLabel();
    int getD();

But these should be const members (they don't change the state).

Yes this is valid:

    vector<Node *> getNeighbors();
    vector<int> getDist();

But like the internal structure I would return a list of edge information (destination and cost as one composite value).

Don't use this->.

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

The only reason to use this-> is to distinguish a local variable from a member variable. This means you have shadowed a member variable with a local. The compiler can not detect when you accidentally forget to use this-> and thus can not generate any errors.

It is better to use very distinct meaningful variable names. That way when you use the wrong name it is easy to spot in the code. Also the compiler can easily detect shadowed variables and warn you about them.

BUT in this case there is no need. You can use itializer lists to solve this issue.

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

In a constructor you should use initializer list.

Node::Node(int label)
    : label(label)     // These are distinct and works as expected.
{}

Also using initializer list makes sure you don't initialize then overwrite a variable.

Put simple one liners in the class declaration:

class Node
{
    void Node::addNeighbor(Node* neighbor) {neighbors.push_back(neighbor);}
    void Node::addDist(int d)              {dist.push_back(d);}
    // etc
}

I mentioned shadowed variables above:

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

// Easier to read understand and let the compiler check written like this:

void Node::setD(int distance) {
    d = distance;
}

I would write a graph like this:

 class Graph
 {
     public:
         class Node
         {
             public:
                 std:vector<Edge> const& getEdges() const;
         };
         class Edge
         {
             public:
                 Node&  getDst()  const;
                 int    getCost() const;
         };
         Node& addNode(std::string const& name);
         void  addEdge(Node& src, Node& dst, int cost);

         Node&  getNode(std::string const& name);
};

Notice: There are no pointers in the interface.

This is fine.

void init(ifstream& f, Node**& nodes, int& n) {

Though I would phrase the interface differently. In C++ we use the input operator operator>> to read a stream into an object. So I would define it like this:

std::istream& operator>>(std::istream& stream, Graph& graph){
{
    graph.load(stream);  // So you need to add a load() method above.
    return stream;
}

In modern C++ it is exceedingly rare to see new/delete.

    nodes = new Node*[n];

Dynamic allocation is usually handled by structures designed to handle the allocation and correct destruction of the memory. In modern C++ this is either a smart pointer (std::unqiue_ptr or std::shared_ptr) or a container (std::vector / std::list / std::map etc)

In this case I would have used std::vector<Node>.

So all this code:

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

Can be replaced by:

    std::vector<Node>  nodes;
    nodes.reserve(n);

Just like not using new/delete above you should not in general be using pointers (yes overly broad). But if the objects can not be nullptr then you should be using references. As you get more advanced pointers creep back in but in general try and stick with references and passing by value.

Here:

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

I would write this to use references (as I don't need to check the value are nullptr.

class Compare {
public:
    bool operator()(Node const& n1, Node const& n2) {
        return n1.getD() > n2.getD();
    }
};

void dijkstra(Node** nodes, int n) {

Yes.

    priority_queue<Node*, vector<Node*>, Compare> queue;

Normally for Dijkstra there are two structures. The ordered list you have. A list of already processed nodes. You seem to be missing the second (I suppose it is stored as part of your graph model).

    do {
        current = queue.top();
        queue.pop();

        // You forgot to check if it has already been processed.
        // Ahhh. I see that you check that in the loop below.
        // The problem is that a node can still be added several times
        // to the priority queue before it is processed.
        //
        // Thus you should check here to see if it has been processed
        // and continue with the next loop if it was processed.
        current->setProccessed(true);

Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

Missing Error Checking

There is no guarantee that the input file input.io exists, so a test after

Return Values From Functions

It is generally better to return values from functions rather than passing in references to variables. It is also better to use C++ container classes rather than old C style arrays in C++. An example of this is the init function. If a vector was used rather than an old C style array the vector could be returned, and the array and count would not need to be passed in by reference. In addition the number of nodes would be contained in the vector so the 2 variables wouldn't be necessary, only the vector is necessary.

Doing this would also simplify the init() function.

std::vector<Node *> init(ifstream &fileIO) {
    size_t n;
    fileIO >> n;

    std::vector<Node *> nodes;

    std::vector<std::vector<int>> adj;
    for (size_t i = 0; i < n; i++) {
        std::vector<int> subAdj;
        for (size_t j = 0; j < n; j++) {
            subAdj.push_back(0);
        }
        adj.push_back(subAdj);
    }

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

    for (size_t i = 0; i < n; i++) {
        nodes.push_back(new Node(i + 1));
    }

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

    return nodes;
}

Reducing the Need to Allocate and Delete Data Structures

Because the code is utilizing old style C arrays and pointers there is memory allocation and memory de-allocation involved. Using a C++ container class such as std::vector would reduce this. Defining the vector within the function as a local variable would allow the variable to be deleted automatically when the function ended as shown above.

Prefer size_t Over int

In C++ it is better to use the size_t type for indexing through arrays and vectors rather than using an int. Generally indexes should never go negative and size_t is unsigned rather than signed.

The this Pointer

Generally in C++ it isn't necessary to use the this pointer to access members of a class. In this code it was necessary because of name collisions between the input variable and the member variable. One way around this in the current code would be to make the member variable names clearer, this would also remove the necessity for comments in the class declaration:

class Node {
    int label;
    int distanceFromOrigin;
    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) {
    label = Label;
}

void Node::setD(int Distance) {
    distanceFromOrigin = Distance;
}