OdinAI

- Main Page
- Namespaces
- Classes
- Files
- Examples

- File List

All Classes Namespaces Functions Variables
DijkstraGraphSearch.h
1 #ifndef ODINAI_DIJKSTRA_GRAPH_SEARCH_H_
2 #define ODINAI_DIJKSTRA_GRAPH_SEARHC_H_
3
4 #include "PriorityQueue.h"
5 #include <list>
6
7 namespace OdinAI
8 {
22 template <class GraphType, class TargetCondition = int>
23 class DijkstraGraphSearch
24 {
25 private:
26 typedef typename GraphType::EdgeType Edge;
27
28 private:
29 const GraphType& m_Graph;
30
31 std::vector<const Edge*> m_ShortestPathTree;
32
33 std::vector<int> m_CostToThisNode;
34
35 std::vector<const Edge*> m_SearchFrontier;
36
37 int m_iSource;
38 int m_iTarget;
39
43 void Search();
44 public:
45
46 DijkstraGraphSearch(const GraphType &graph,
47 int source,
48 int target=-1) :
49 m_Graph(graph),
50 m_ShortestPathTree(graph.NumNodes()),
51 m_SearchFrontier(graph.NumNodes()),
52 m_CostToThisNode(graph.NumNodes()),
53 m_iSource(source),
54 m_iTarget(target)
55 {
56 Search();
57 }
58
63 std::vector<const Edge*> GetSPT() const{ return m_ShortestPathTree; }
64
69 std::list<int> GetPath() const;
70
75 int GetCostToTarget()const{ return m_CostToThisNode[m_iTarget]; }
76
81 int GetCostToNode(unsigned int nd) const { return m_CostToThisNode[nd]; }
82 };
83
84 template <class GraphType, class TargetCondition>
85 void DijkstraGraphSearch<GraphType, TargetCondition>::Search()
86 {
87 IndexedPriorityQLow<double> pq(m_CostToThisNode, m_Graph.NumNodes());
88
89 pq.insert(m_iSource);
90
91 // While the queue is not empty
92 while(!pq.empty())
93 {
94 int nextClosestNode = pq.Pop();
95
96 m_ShortestPathTree[NextClosestNode] = m_SearchFrontier[nextClosestNode];
97
98 if ((m_iTarget != 1 && nextClosestNode == m_iTarget) || (m_iTarget == -1 && TargetCondition::)
99 {
100 m_iTarget = NextClosestNode;
101 return;
102 }
103
104 GraphType::ConstEdgeIterator ConstEdgeItr(m_Graph, nextClosestNode);
105 for (const Edge* pE=ConstEdgeItr.begin();
106 !ConstEdgeItr.end();
107 pE=ConstEdgeItr.next())
108 {
109 int NewCost = m_CostToThisNode[nextClosestNode] + pE->Cost();
110
111 if (m_SearchFrontier[pE->To()] == nullptr)
112 {
113 m_CostToThisNode[pE->To()] = NewCost;
114
115 pq.insert(pE->To());
116
117 m_SearchFrontier[pE->To()] = pE;
118 }
119 else if ((NewCost < m_CostToThisNode[pE->To()]) &&
120 (m_ShortestPathTree[pE->To()] == nullptr))
121 {
122 m_CostToThisNode[pE->To()] = NewCost;
123
124 pq.ChangePriority(pE->To());
125
126 m_SearchFrontier[pE->To()] = pE;
127 }
128 }
129 }
130 }
131
132 //-----------------------------------------------------------------------------
133 template <class GraphType, class TargetCondition>
134 std::list<int> DijkstraGraphSearch<GraphType, TargetCondition>::GetPath() const
135 {
136 std::list<int> path;
137
138 //just return an empty path if no target or no path found
139 if (m_iTarget < 0) return path;
140
141 int nd = m_iTarget;
142 path.push_front(nd);
143
144 while ((nd != m_iSource) && (m_ShortestPathTree[nd] != nullptr))
145 {
146 nd = m_ShortestPathTree[nd]->From();
147
148 path.push_front(nd);
149 }
150
151 return path;
152 }
153 }
154 #endif
OdinAI::DijkstraGraphSearch
Given a graph, and an optional target, it calculates the shortest path from the source node to the ta...
Definition: DijkstraGraphSearch.h:23
OdinAI::DijkstraGraphSearch::GetPath
std::list< int > GetPath() const
Definition: DijkstraGraphSearch.h:134
OdinAI::DijkstraGraphSearch::GetSPT
std::vector< const Edge * > GetSPT() const
Definition: DijkstraGraphSearch.h:63
OdinAI::DijkstraGraphSearch::GetCostToNode
int GetCostToNode(unsigned int nd) const
Definition: DijkstraGraphSearch.h:81
OdinAI::DijkstraGraphSearch::GetCostToTarget
int GetCostToTarget() const
Definition: DijkstraGraphSearch.h:75