Attempt at Dijkstra's algorithm

Question

I tried to implement Dijkstra algorithm in C++ 11. Is this a good implementation of Dijkstra algorithm in C++ or not? I have overloaded -= and += operators to make the code more easier to read. These operators are used to add and remove nodes from the object of MyList class which is inherited by vector for vector like functions.

#include<vector>
#include<iostream>
#include<algorithm>
#include<conio.h>


using namespace std;


const int MAXROW = 4;
const int MAXCOL = 4;

/*

-UML DIAGRAM-

Class Node                                              |
________________________________________________________|
-costSoFar:int                                          |
-row:int                                                |
-col:int                                                |
-from:Node*                                             |
________________________________________________________|
+Node():Node                                            |
+Node(int,int,int,Node*):Node*                          |
+getRow():int                                           |
+getCol():int                                           |
+setCostSoFar(int):void                                 |
+getCostSoFar():int                                     |
+setFromNode(Node*):void                                |
+getFromNode():Node*                                    |
+operator == (const Node*):bool                         |
+operator != (const Node*):bool                         |
+blockNumber(int,int):static int                        |
+getAdjNodes(Node*,Node*[]):static std::vector<Node*>   |
________________________________________________________|


*/
class Node
{
    int costSoFar;
    int row, col;
    Node *from;
public:

    Node() {}

    Node(int aCostSoFar, int aRow, int aCol, Node *aFrom) : costSoFar(aCostSoFar), row(aRow), col(aCol), from(aFrom)
    {}

    //returns row of this node in map
    inline int getRow() { return row; }

    //returns col of this node in map
    inline int getCol() { return col; }

    //sets the cost so far of this node
    void setCostSoFar(int costSoFar) { this->costSoFar = costSoFar; }

    //returns the current cost so of this node
    int getCostSoFar() { return costSoFar; }

    //sets the from node
    void setFromNode(Node*);

    //returns the from node
    Node* getFromNode() { return from; }

    //compares the "this" to other Node...returns true if both are equal otherwise false
    bool operator == (const Node*);

    //compares the "this" to other Node...returns true if both are unequal otherwise false
    bool operator != (const Node*);

    //to get the exact index 
    inline static int Node::blockNumber(int row, int col)
    {
        return MAXROW * row + col;
    }

    //returns Nodes which are adjacent to Node*
    static std::vector<Node*> getAdjNodes(Node*, Node*[]);

};

//definitions of class Node member functions
void Node::setFromNode(Node * current)
{
    this->from = current;
}


bool Node::operator==(const Node* other)
{
    return (other->col == this->col) && (other->row == this->row);
}

bool Node::operator!=(const Node*other)
{
    return (other->col != this->col) || (other->row != this->row);
}


std::vector<Node*> Node::getAdjNodes(Node* current, Node *nMap[])
{
    std::vector<Node*> nodes;

    if (current->getRow() < MAXROW - 1)
        nodes.push_back(nMap[Node::blockNumber(current->getRow() + 1, current->getCol())]);

    if (current->getCol() < MAXCOL - 1)
        nodes.push_back(nMap[Node::blockNumber(current->getRow(), current->getCol() + 1)]);

    if (current->getCol() > 0)
        nodes.push_back(nMap[Node::blockNumber(current->getRow(), current->getCol() - 1)]);

    if (current->getRow() > 0)
        nodes.push_back(nMap[Node::blockNumber(current->getRow() - 1, current->getCol())]);

    if (current->getRow()<MAXROW - 1 && current->getCol()>0)
        nodes.push_back(nMap[Node::blockNumber(current->getRow() + 1, current->getCol() - 1)]);

    if (current->getRow()>0 && current->getCol()<MAXCOL - 1)
        nodes.push_back(nMap[Node::blockNumber(current->getRow() - 1, current->getCol() + 1)]);

    if (current->getRow()>0 && current->getCol()>0)
        nodes.push_back(nMap[Node::blockNumber(current->getRow() - 1, current->getCol() - 1)]);

    if (current->getRow()<MAXROW - 1 && current->getCol()<MAXCOL - 1)
        nodes.push_back(nMap[Node::blockNumber(current->getRow() + 1, current->getCol() + 1)]);

    return nodes;
}

/* *** End of class Node*** */



/*

-UML DIAGRAM-

Class MyList
____________________________|
+operator +=(Node*):void    |
+operator !=(Node*):void    |
+contains(Node*):bool       |
____________________________|

public std::vector<Node*> <------- MyList
 */
class MyList : public std::vector<Node*>
{
public:
    //adds the node to the list
    void operator +=(Node*);
    //removes the particular node from the list
    void operator -=(Node*);
    //checks whether the current list contains particular node....if it contains then it will return true else will return false.
    bool contains(Node*);
    //returns the node which is at the begining of the list
    Node* getFirstNode();

};


void MyList::operator+=(Node* obj)
{

    this->push_back(obj);
}


void MyList::operator-=(Node* obj)
{
    auto  iter = std::remove(this->begin(), this->end(), obj);
    this->erase(iter, this->end());
}


bool MyList::contains(Node* obj)
{
    for (vector<Node*>::iterator iter = this->begin(); iter != this->end(); iter++) {
        if ((*iter)->operator==(obj)) return true;
    }
    return false;
}


Node* MyList::getFirstNode()
{
    auto iter = begin();
    return *iter;
}


//function used to reverse the contents of the vector to get the final path
void reverse(std::vector<int> &v)
{
    auto iter1 = v.begin();
    auto iter2 = v.end();
    iter2--;
    for (int i = 0; i < v.size()/2; i++)
    {

        *iter1 = *iter1 + *iter2;
        *iter2 = *iter1 - *iter2;
        *iter1 = *iter1 - *iter2;

        iter1++;
        iter2--;
    }
}


std::vector<int> dijsktra(const int *map, Node *startNode, Node* goalNode)
{
    Node* nMap[MAXROW*MAXCOL];

    for (int row = 0; row < MAXROW; row++)
    {
        for (int col = 0; col < MAXCOL; col++)
        {
            if (row == startNode->getRow() && col == startNode->getCol())
                nMap[Node::blockNumber(row, col)] = startNode;
            if (row == goalNode->getRow() && col == goalNode->getCol())
                nMap[Node::blockNumber(row, col)] = goalNode;

            nMap[Node::blockNumber(row, col)] = new Node(map[Node::blockNumber(row, col)], row, col, 0);
        }
    }


    Node *current = 0;


    MyList openList;
    MyList closedList;

    openList += startNode;

    while (openList.size() > 0)
    {

        current = openList.getFirstNode();

        if (*current == (goalNode))
            break;


        std::vector<Node*> adjNodes = Node::getAdjNodes(current, nMap);

        for (Node* node : adjNodes)
        {


            int totalCostSoFar = current->getCostSoFar() + map[Node::blockNumber(node->getRow(), node->getCol())];

            if (closedList.contains(node))
                continue;


            if (openList.contains(node))
            {
                if (node->getCostSoFar() <= totalCostSoFar)
                    continue;
                else
                {

                    node->setCostSoFar(totalCostSoFar);
                    node->setFromNode(current);


                }

            }
            else
            {

                node->setCostSoFar(totalCostSoFar);
                node->setFromNode(current);
                openList += node;
            }
        }

        openList -= current;
        closedList += current;


    }

    std::vector<int> path;

    if (*current != goalNode)
        std::cout << "failed to find the goal node in map!" << std::endl;
    else
    {
        while (current->operator!=(startNode))
        {
            path.push_back(Node::blockNumber(current->getRow(), current->getCol()));
            current = current->getFromNode();
        }
    }

    path.push_back(Node::blockNumber(startNode->getRow(), startNode->getCol()));

    for (int row = 0; row < MAXROW; row++)
    {
        for (int col = 0; col < MAXCOL; col++)
            delete nMap[Node::blockNumber(row, col)];
    }

    reverse(path);
    return path;
}




int main()
{

    //our 4X4 map
    //index 0 is our start node and index 15 is our goal node
    int map[] =
    {
        1,1,1,1,
        2,10,1,1,
        1,1,10,1,
        1,1,1,1
    };

    Node* startNode = new Node(1, 0, 0, 0);
    Node* goalNode = new Node(2, 3, 3, 0);

    std::vector<int> path = dijsktra(map, startNode, goalNode);

    for (int v : path)
        cout << v << endl;

    _getch();

    return 0;
}

Answer 1

Just a couple of minor points:

1. This does not compile by g++:

   inline static int Node::blockNumber(int row, int col)
   {
       return MAXROW * row + col;
   }
   

   It seems to be a Visual Studio trick. In order to make your code compile with g++, just remove Node::.

2. The following can be rewritten:

   if (openList.contains(node))
   {
       if (node->getCostSoFar() <= totalCostSoFar)
           continue;
       else         
       {
           node->setCostSoFar(totalCostSoFar);
           node->setFromNode(current);
       }
   }
   

   to

   if (openList.contains(node))
   {
       if (node->getCostSoFar() > totalCostSoFar)
       {
           node->setCostSoFar(totalCostSoFar);
           node->setFromNode(current);
       }
   }
   

3. It seems like you are assigning weights on nodes and not on arcs. This is perfectly OK since sometimes that is exactly what we want to do. However, the following input will fail:

   int map[] =
   {
       1,   1,   1,   1,
       100, 100, 100, 1,
       1,   1,   1,   1,
       1, 100, 100, 100
   };
   
   Node* startNode = new Node(1, 0, 0, 0);
   Node* goalNode = new Node(2, 3, 0, 0);
   

   by returning

   0
   4 
   8
   12 
   

   The problem here is that your "Dijkstra" is actually a breadth-first search since your open list is not a priority queue but rather a simple queue (which is the essential difference between Dijkstra and BFS). In order to deal with it, add a method to your MyList:

   void MyList::sort() 
   {
       std::sort(begin(), end(), my_less);
   }
   

   and call it whenever you do +=. my_less would look like:

   bool my_less(Node* a, Node* b) 
   {
       return a->getCostSoFar() < b->getCostSoFar();
   }
   

   The above arrangement will print:

   0
   1
   2 
   7
   10
   9
   12
   

   as it should.