Dijkstra's algorithm is a graph traversal algorithm similar to BFS, but it takes into account the weight of the edges. It uses a priority list to visit the nodes with the smallest cost first and a set to keep track of the visited nodes. A came_from map can be used to store the parent node of each node to create a pathfinding algorithm.
It uses the producer-consumer pattern, where the producer is the algorithm that adds the nodes to the priority queue and the consumer is the algorithm that removes the nodes from the priority queue and do the work.
The algorithm is greedy and works well with positive weights. It is not optimal for negative weights, for that you should use the Bellman-Ford algorithm.
// node registry// K is the key type for indexing the nodes, usually it can be a string or an integer// Node is the Node type to store node related data unordered_map<K,N>nodes;// K is the key type of the index// W is the weight type of the edge, usually it can be an integer or a float// W can be more robust and become a struct, for example, to store the weight and the edge name// if W is a struct, remember no implement the < operator for the priority queue work// unordered_map is used to exploit the O(1) access time and be tolerant to sparse keysunordered_map<K,unordered_map<K,W>>edges;// usage// the cost from node A to node B is 5edges["A"]["B"]=5;// if you want to make it bidirectional set the opposite edge too// edges["B"]["A"] = 5;
For the algoritm to work we will need a priority queue to store the nodes to be visited:
// priority queue to store the nodes to be visited// C is the W type and stores the accumulated cost to reach the node// K is the key type of the index of the nodepriority_queue<pair<C,K>>frontier;
For the visited nodes we will use a set:
// set to store the visited nodes// K is the key type of the index of the nodeunordered_set<K>visited;
Example of Dijkstra's algorithm in C++ to build a path from the start node to the end node:
#include<iostream>#include<unordered_map>#include<unordered_set>#include<string>#include<queue>usingnamespacestd;// DijikstrastructNode{// add your custom data herestringname;};// nodes indexed by idunordered_map<uint64_t,Node>nodes;// edges indexed by source id and destination id, the value is theunordered_map<uint64_t,unordered_map<uint64_t,double>>edges;// priority queue for the frontier// this could be declared inside the Dijkstra functionpriority_queue<pair<double,uint64_t>>frontier;// optionally, in order to create a pathfinding, use came_from map to store the parent nodeunordered_map<uint64_t,uint64_t>came_from;// cost to reach the node so farunordered_map<uint64_t,double>cost_so_far;voidVisit(Node*node){// add your custom code herecout<<node->name<<endl;}voidDijkstra(uint64_tstart_id){cout<<"Visiting nodes:"<<endl;// clear the costs so farcost_so_far.clear();// boostrap the frontier// 0 means the cost to reach the start node is 0frontier.emplace(0,start_id);cost_so_far[start_id]=0;// while there are nodes to visitwhile(!frontier.empty()){// get the node with the lowest costauto[cost,current_id]=frontier.top();frontier.pop();// get the nodeNode*current=&nodes[current_id];// visit the nodeVisit(current);// for each neighborfor(constauto&[neighbor_id,edge_cost]:edges[current_id]){// calculate the new cost to reach the neighbordoublenew_cost=cost_so_far[current_id]+edge_cost;// if the neighbor is not visited yet or the new cost is less than the previous costif(!cost_so_far.contains(neighbor_id)||new_cost<cost_so_far[neighbor_id]){// update the costcost_so_far[neighbor_id]=new_cost;// add the neighbor to the frontierfrontier.emplace(new_cost,neighbor_id);// update the parent nodecame_from[neighbor_id]=current_id;}}}}intmain(){// build the graphnodes[0]={"A"};// this will be our startnodes[1]={"B"};nodes[2]={"C"};nodes[3]={"D"};// this will be our end// store the edges costsedges[0][1]=1;edges[0][2]=2;edges[0][3]=100;// this is a very expensive edgeedges[1][3]=3;edges[2][3]=1;// the path from 0 to 3 is A -> C -> D even though the edge A -> D have less stepsDijkstra(0);// print the path from the end to the startcout<<"Path:"<<endl;uint64_tindex=3;// prevents infinite loop if the end is unreachableif(!came_from.contains(index)){cout<<"No path found"<<endl;return0;}while(index!=0){cout<<nodes[index].name<<endl;index=came_from[index];}cout<<nodes[0].name<<endl;return0;}