1 #ifndef ODINAI_DIJKSTRA_GRAPH_SEARCH_H_
2 #define ODINAI_DIJKSTRA_GRAPH_SEARHC_H_
4 #include "PriorityQueue.h"
22 template <
class GraphType,
class TargetCondition =
int>
26 typedef typename GraphType::EdgeType Edge;
29 const GraphType& m_Graph;
31 std::vector<const Edge*> m_ShortestPathTree;
33 std::vector<int> m_CostToThisNode;
35 std::vector<const Edge*> m_SearchFrontier;
50 m_ShortestPathTree(graph.NumNodes()),
51 m_SearchFrontier(graph.NumNodes()),
52 m_CostToThisNode(graph.NumNodes()),
63 std::vector<const Edge*>
GetSPT()
const{
return m_ShortestPathTree; }
81 int GetCostToNode(
unsigned int nd)
const {
return m_CostToThisNode[nd]; }
84 template <
class GraphType,
class TargetCondition>
85 void DijkstraGraphSearch<GraphType, TargetCondition>::Search()
87 IndexedPriorityQLow<double> pq(m_CostToThisNode, m_Graph.NumNodes());
94 int nextClosestNode = pq.Pop();
96 m_ShortestPathTree[NextClosestNode] = m_SearchFrontier[nextClosestNode];
98 if ((m_iTarget != 1 && nextClosestNode == m_iTarget) || (m_iTarget == -1 && TargetCondition::)
100 m_iTarget = NextClosestNode;
104 GraphType::ConstEdgeIterator ConstEdgeItr(m_Graph, nextClosestNode);
105 for (
const Edge* pE=ConstEdgeItr.begin();
107 pE=ConstEdgeItr.next())
109 int NewCost = m_CostToThisNode[nextClosestNode] + pE->Cost();
111 if (m_SearchFrontier[pE->To()] ==
nullptr)
113 m_CostToThisNode[pE->To()] = NewCost;
117 m_SearchFrontier[pE->To()] = pE;
119 else if ((NewCost < m_CostToThisNode[pE->To()]) &&
120 (m_ShortestPathTree[pE->To()] ==
nullptr))
122 m_CostToThisNode[pE->To()] = NewCost;
124 pq.ChangePriority(pE->To());
126 m_SearchFrontier[pE->To()] = pE;
133 template <
class GraphType,
class TargetCondition>
139 if (m_iTarget < 0)
return path;
144 while ((nd != m_iSource) && (m_ShortestPathTree[nd] !=
nullptr))
146 nd = m_ShortestPathTree[nd]->From();
Given a graph, and an optional target, it calculates the shortest path from the source node to the ta...
Definition: DijkstraGraphSearch.h:23
std::list< int > GetPath() const
Definition: DijkstraGraphSearch.h:134
std::vector< const Edge * > GetSPT() const
Definition: DijkstraGraphSearch.h:63
int GetCostToNode(unsigned int nd) const
Definition: DijkstraGraphSearch.h:81
int GetCostToTarget() const
Definition: DijkstraGraphSearch.h:75