I started to implement routing algorithms and I began with the easiest one first: Dijkstra.
It’s a kind of greedy algorithm which calculates a shortest path from one node to another one in a graph.
The edges of the graph can have weights – if no weights are needed then assume 1 as the weight of each edge.
You need a priority queue in order to work through the graph and find the shortest path.
When using Fibonacci Heaps for implementing the priority queue then the runtime complexity is O(n * log(n) + m).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
/**************************************************************** classes that are used. source code will be added later... class ShortestPathNode; class ShortestPathAlgorithm; class DijkstraNode : public ShortestPathNode; class Dijkstra : public ShortestPathAlgorithm; *****************************************************************/ ShortestPathNode* Dijkstra::internalCalculation() { assert(this->m_StartNode != nullptr && this->m_StartNode->getGraphNode() != nullptr); assert(this->m_EndNode != nullptr && this->m_EndNode->getGraphNode() != nullptr); m_TodoQueue.clear(); m_TodoQueue = Fibonacci::FibonacciHeap<ShortestPathNode>(); std::shared_ptr<Node> startNode = this->m_StartNode->getGraphNode(); std::shared_ptr<Node> endNode = this->m_EndNode->getGraphNode(); this->preProcess(); while (!this->m_TodoQueue.empty() && !this->m_AbortCalculation) { Fibonacci::Node<ShortestPathNode>* heapNode = this->m_TodoQueue.extractMin(); DijkstraNode* node = static_cast<DijkstraNode*>(heapNode->getValue()); if (node->getGraphNode() == endNode) { if (this->m_FinishedCallback != nullptr) { double totalWeight = this->getTotalWeightFromStart(node); this->m_FinishedCallback(true, node, totalWeight); } return node; } // iterate all neighbour node std::set<std::shared_ptr<Edge> > edges = node->getGraphNode()->getEdges(); std::set<std::shared_ptr<Edge> >::iterator it; for (it = edges.begin(); it != edges.end(); it++) { std::shared_ptr<Edge> e = *it; // get the neighbour Node std::shared_ptr<Node> dest = e->getDestinationNode(); // Get the DijkstraNode object for this Node DijkstraNode* destNode = static_cast<DijkstraNode*>(this->m_MappingGraphNode2ShortestPathNode[dest]); // now call stepCallback if available if (this->m_StepCallback != nullptr) { this->m_StepCallback(e); } // Calculate the distance for the neighbour Node double distance = e->getWeight() + node->getDistance(); // If the calculated distance is lower than the already stored distance... if (destNode->getDistance() > distance) { // ...then update the distance to the lower value destNode->setDistance(distance); // and set the Node as predecessor to this neighbour Node destNode->setPredecessor(node); destNode->setWeightToPredecessor(e->getWeight()); // update the queue Fibonacci::Node<ShortestPathNode>* updateNode = this->m_TodoQueue.findByValue(destNode); this->m_TodoQueue.decreaseKey(updateNode, distance); } } } if (this->m_AbortCalculation) { this->m_TodoQueue.clear(); return nullptr; } if (this->m_FinishedCallback != nullptr) this->m_FinishedCallback(false, nullptr, 0); return nullptr; } void Dijkstra::preProcess() { m_TodoQueue.clear(); m_MappingGraphNode2ShortestPathNode.clear(); std::set<std::shared_ptr<Node>>::iterator it; std::set<std::shared_ptr<Node>> nodes = this->m_Graph->getNodes(); for (it = nodes.begin(); it != nodes.end(); ++it) { std::shared_ptr<Node> n = *it; DijkstraNode* node = new DijkstraNode(); // sets predecessor to 0 and distance to INT_MAX node->setGraphNode(n); Fibonacci::Node<ShortestPathNode>* heapNode = new Fibonacci::Node<ShortestPathNode>(node->getDistance(), node); this->m_TodoQueue.insert(heapNode); if (node->getGraphNode() == this->m_StartNode->getGraphNode()) { node->setDistance(0); this->m_TodoQueue.decreaseKey(heapNode, 0); } this->m_MappingGraphNode2ShortestPathNode[n] = node; } } |