Adjacency List Graph - Dijkstra's Algorithm
/******************************************************************************/
/*!
Dijkstra's Algorithm to find the greedy
path from any node to every other node
\param start_node
The node that the algorithm will start at
\return
A vector of DijkstraInfo structs
*/
/******************************************************************************/
std::vector<DijkstraInfo> ALGraph::Dijkstra(unsigned start_node) const
{
unsigned evaluated_nodes = 0;
std::vector<DijkstraInfo> dijkstra_list;
std::greater<GNode> cmp;
std::priority_queue<GNode, std::vector<GNode>, std::greater<GNode> > node_pq(cmp);
std::list<GNode>::iterator node_list_itr = node_list_.begin();
GNode* temp_node_x = NULL;
GNode* temp_node_y = NULL;
//Find the starting Node
while(node_list_itr->node_id_ != start_node && node_list_itr != node_list_.end())
++node_list_itr;
//Initialize the source cost to 0
node_list_itr->cost = 0;
//mark as evaluated
node_list_itr->evaluated = true;
++evaluated_nodes;
node_list_itr->shortest_path = UpdatePath(&*node_list_itr);
//For each node adjacent to the source, calling it temp_node_y
std::list<GEdge>::iterator edge_itr = node_list_itr->edge_list_.begin();
while(edge_itr != node_list_itr->edge_list_.end())
{
//Relax the node
temp_node_y = edge_itr->edge_to_node_;
temp_node_y->cost = edge_itr->edge_weight_;
//Add source node as predecessor of temp_node_y
temp_node_y->predecessor = &*node_list_itr;
//Place the node into the priority queue
node_pq.push(*temp_node_y);
++edge_itr;
}
//While there are nodes in the graph that haven't been evaluated
while(evaluated_nodes != graph_size_ && node_pq.size() > 0)
{
//Remove a node, temp_node_x, from the PQ (lowest total cost)
unsigned id = node_pq.top().node_id_;
std::list<GNode>::iterator search_itr = node_list_.begin();
while(search_itr->node_id_ != id && search_itr != node_list_.end())
++search_itr;
temp_node_x = &*search_itr;
node_pq.pop();
//If the node hasn't already been evaluated
if(temp_node_x->evaluated == false)
{
//Mark temp_node_x as evaluated
temp_node_x->evaluated = true;
++evaluated_nodes;
temp_node_x->shortest_path = UpdatePath(temp_node_x);
//For each neighbor, temp_node_y, of temp_node_x
edge_itr = temp_node_x->edge_list_.begin();
while(edge_itr != temp_node_x->edge_list_.end())
{
if(edge_itr->edge_to_node_->evaluated == false)
{
//Relax y
temp_node_y = edge_itr->edge_to_node_;
//If new cost to reach temp_node_y is less than the current cost
if(edge_itr->edge_weight_ + temp_node_x->cost < temp_node_y->cost)
{
//Update list of nodes (path) to y from source.
temp_node_y->cost = edge_itr->edge_weight_ + temp_node_x->cost;
temp_node_y->predecessor = temp_node_x;
//Place temp_node_y in the priority queue
node_pq.push(*temp_node_y);
}
}
++edge_itr;
}
}
}
//Build the Dijkstra table
node_list_itr = node_list_.begin();
while(node_list_itr != node_list_.end())
{
DijkstraInfo d_info;
d_info.cost = node_list_itr->cost;
d_info.path = node_list_itr->shortest_path;
dijkstra_list.push_back(d_info);
++node_list_itr;
}
return dijkstra_list;
}
/*!
Dijkstra's Algorithm to find the greedy
path from any node to every other node
\param start_node
The node that the algorithm will start at
\return
A vector of DijkstraInfo structs
*/
/******************************************************************************/
std::vector<DijkstraInfo> ALGraph::Dijkstra(unsigned start_node) const
{
unsigned evaluated_nodes = 0;
std::vector<DijkstraInfo> dijkstra_list;
std::greater<GNode> cmp;
std::priority_queue<GNode, std::vector<GNode>, std::greater<GNode> > node_pq(cmp);
std::list<GNode>::iterator node_list_itr = node_list_.begin();
GNode* temp_node_x = NULL;
GNode* temp_node_y = NULL;
//Find the starting Node
while(node_list_itr->node_id_ != start_node && node_list_itr != node_list_.end())
++node_list_itr;
//Initialize the source cost to 0
node_list_itr->cost = 0;
//mark as evaluated
node_list_itr->evaluated = true;
++evaluated_nodes;
node_list_itr->shortest_path = UpdatePath(&*node_list_itr);
//For each node adjacent to the source, calling it temp_node_y
std::list<GEdge>::iterator edge_itr = node_list_itr->edge_list_.begin();
while(edge_itr != node_list_itr->edge_list_.end())
{
//Relax the node
temp_node_y = edge_itr->edge_to_node_;
temp_node_y->cost = edge_itr->edge_weight_;
//Add source node as predecessor of temp_node_y
temp_node_y->predecessor = &*node_list_itr;
//Place the node into the priority queue
node_pq.push(*temp_node_y);
++edge_itr;
}
//While there are nodes in the graph that haven't been evaluated
while(evaluated_nodes != graph_size_ && node_pq.size() > 0)
{
//Remove a node, temp_node_x, from the PQ (lowest total cost)
unsigned id = node_pq.top().node_id_;
std::list<GNode>::iterator search_itr = node_list_.begin();
while(search_itr->node_id_ != id && search_itr != node_list_.end())
++search_itr;
temp_node_x = &*search_itr;
node_pq.pop();
//If the node hasn't already been evaluated
if(temp_node_x->evaluated == false)
{
//Mark temp_node_x as evaluated
temp_node_x->evaluated = true;
++evaluated_nodes;
temp_node_x->shortest_path = UpdatePath(temp_node_x);
//For each neighbor, temp_node_y, of temp_node_x
edge_itr = temp_node_x->edge_list_.begin();
while(edge_itr != temp_node_x->edge_list_.end())
{
if(edge_itr->edge_to_node_->evaluated == false)
{
//Relax y
temp_node_y = edge_itr->edge_to_node_;
//If new cost to reach temp_node_y is less than the current cost
if(edge_itr->edge_weight_ + temp_node_x->cost < temp_node_y->cost)
{
//Update list of nodes (path) to y from source.
temp_node_y->cost = edge_itr->edge_weight_ + temp_node_x->cost;
temp_node_y->predecessor = temp_node_x;
//Place temp_node_y in the priority queue
node_pq.push(*temp_node_y);
}
}
++edge_itr;
}
}
}
//Build the Dijkstra table
node_list_itr = node_list_.begin();
while(node_list_itr != node_list_.end())
{
DijkstraInfo d_info;
d_info.cost = node_list_itr->cost;
d_info.path = node_list_itr->shortest_path;
dijkstra_list.push_back(d_info);
++node_list_itr;
}
return dijkstra_list;
}