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;
}
Aucun commentaire:
Enregistrer un commentaire