# Attempt at Dijkstra's algorithm

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                        |
________________________________________________________|

*/
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*

};

//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*> 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;

{

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;
}

• It's not dijkstr but breadth first search you'll need to keep openList sorted by Node::getCostSoFar() for it to be dijkstra Jan 6, 2016 at 16:05
• What is the point of keeping it sorted?? Jan 7, 2016 at 1:59
• So you can easily get the node with the lowest CostSoFar (a requirement for dijkstra) Jan 7, 2016 at 8:53
• and let's remove conio.h for portablity unless you're trying to go back in time. Jan 14, 2016 at 18:42
• @AbhinavGauniyal yeah! I forgot that one! I made a lot of changes since I posted this. Thank you for taking some time out for this. Jan 14, 2016 at 18:54

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.

• That was really a good advice. Thanks for taking out some time for this code! Jan 8, 2016 at 16:23