dijkstra00.cpp

#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <string>

using namespace std;


const char FLOOR = '1' ;
const char WALL  = '0' ;
const char GOAL  = 'G' ;

const int MapWidth = 10, MapHeight = 10;
//       Y pos      X pos
char Map[MapHeight][MapWidth] = {
    { '1', '1', 'G', '1', '1', '1', '1', '1', '1', '1' },
    { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
    { '1', '1', '0', '1', '1', '1', '1', '1', '0', 'G' },
    { '1', '1', '0', '0', '1', '1', '1', '1', '0', '1' },
    { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
    { '1', '1', '1', '1', '1', '1', '1', '0', '0', '1' },
    { '1', '1', '1', '1', '1', '1', '1', '0', '1', '1' },
    { '1', '1', '1', '0', '0', '1', '1', '0', '1', '1' },
    { '1', '1', '0', '0', '0', '1', '1', '0', '0', '0' },
    { '1', '1', '1', 'G', '0', '1', '1', '1', '1', '1' }
};

struct Pos
{
    short x,y;
	Pos operator + ( Pos p ) const { return Pos(x+p.x,y+p.y); }
	bool operator < ( Pos p ) const { return ( y==p.y ) ? (x<p.x) : (y<p.y) ; }
	bool operator != ( Pos p ) const { return ( y!=p.y ) || (x!=p.x) ; }
    Pos(short x=0,short y=0) : x(x), y(y) {}
};

bool valid(Pos p) { return p.x>=0 && p.x<MapWidth && p.y>=0 && p.y<MapHeight; }

enum Dir { d_beg, d_up=d_beg, d_rg, d_dn, d_lf, d_end };

Pos deltas[d_end] = { {0,-1}, {+1,0}, {0,+1}, {-1,0} };

Dir& operator ++ ( Dir& d ) { d = (Dir) ( 1+(int)d ) ; return d; }

Dir other(Dir d)
{
	switch(d)
	{
	case d_up: return d_dn;
	case d_rg: return d_lf;
	case d_dn: return d_up;
	case d_lf: return d_rg;
	default: return d_end;
	}
}

struct SearchMapItem
{
	bool traversble;
	bool goal;
	bool visited;
	int cost_here;
	Dir came_from;
	bool paths[d_end];
};

map<Pos,SearchMapItem> search_map;
typedef map<Pos,SearchMapItem>::iterator SMII;

void MakeMap()
{
	search_map.clear();
	Pos p;
	for(p.y=0;p.y<MapHeight;++p.y) for(p.x=0;p.x<MapWidth;++p.x) 
	{
		SearchMapItem smi;
		smi.visited = false;
		smi.cost_here = -1;
		smi.came_from = d_end;
		if( Map[p.y][p.x] == WALL )
		{
			smi.traversble = false;
		}
		else if( Map[p.y][p.x] == GOAL )
		{
			smi.traversble = true;
			smi.goal = true;
		}
		else if( Map[p.y][p.x] == FLOOR )
		{
			smi.traversble = true;
			smi.goal = false;
			for( Dir d = d_beg; d != d_end; ++d )
			{
				Pos p2 = p + deltas[d];
				smi.paths[d] = valid(p2) && (Map[p2.y][p2.x] != WALL) ;
			}
		}
		search_map[p] = smi;
	}
}

void FindGoalFrom( Pos start )
{
	vector<SMII> found;

	{
		SMII smii = search_map.find(start);

		if(smii==search_map.end()) { cout << "starting outside map\n"; return; }
		if(smii->second.goal) { cout << "already at target\n"; return; }
		if(!smii->second.traversble) { cout << "starting in a wall\n"; return; }

		smii->second.visited = true;
		smii->second.cost_here = 0;
		found.push_back(smii);
	}

	int cost_so_far = 0;
	bool did_find = false;

	while(!did_find)
	{

		vector<SMII> candidates;

		for( SMII smii : found )
		{
			for( Dir d = d_beg; d != d_end; ++d )
			{
				if( ! smii->second.paths[d] ) continue;
				Pos p = smii->first + deltas[d];
				if(!valid(p)) continue;
				SMII cand = search_map.find(p);
				if(cand==search_map.end()) continue;
				if(cand->second.visited) continue;
				cand->second.came_from=d;
				candidates.push_back(cand);
			}
		}

		++cost_so_far;

		if( candidates.empty() ) break;

		for( SMII smii : candidates )
		{
			smii->second.visited = true;
			smii->second.cost_here = cost_so_far;
			found.push_back(smii);
			if( smii->second.goal ) { did_find = true; break; }
		}

	}

	if( ! did_find ) { cout << "no goal reachable\n"; return; }

	SMII pos = found.back();

	vector<Dir> path;

	while( pos->first != start )
	{
		Dir d = pos->second.came_from;
		path.push_back(d);
		Pos p = pos->first + deltas[ other(d) ];
		pos = search_map.find(p);
	}

	for( auto itr = path.rbegin(); itr != path.rend(); ++itr )
	{
		const char* dir_names[] = { "Up", "Right", "Down", "Left" } ;
		cout << "Walk " << dir_names[*itr] << endl;
	}
	cout << "Then you are at goal in total " << to_string(cost_so_far) << " steps" << endl;
}

int main()
{
    MakeMap();
    
    FindGoalFrom( Pos(5,9) );
    
    cout << "\ndone\n";
}

dijkstra01.cpp

#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <string>

using namespace std;


#include <sstream>
#include <string>

template <typename T>
std::string to_string(const T& value)
{
    std::ostringstream oss;
    oss << value;

    return oss.str();
}

const int MapWidth = 4, MapHeight = 3;
//       Y pos      X pos
char Map[MapHeight][MapWidth] = {
                 {'X','1','S','3'},
                 {'4','2','X','4'},
                 {'X','1','D','2'}
//    { '1', '1', 'G', '1', '1', '1', '1', '1', '1', '1' },
//    { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
//    { '1', '1', '0', '1', '1', '1', '1', '1', '0', 'G' },
//    { '1', '1', '0', '0', '1', '1', '1', '1', '0', '1' },
//    { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
//    { '1', '1', '1', '1', '1', '1', '1', '0', '0', '1' },
//    { '1', '1', '1', '1', '1', '1', '1', '0', '1', '1' },
//    { '1', '1', '1', '0', '0', '1', '1', '0', '1', '1' },
//    { '1', '1', '0', '0', '0', '1', '1', '0', '0', '0' },
//    { '1', '1', '1', 'G', '0', '1', '1', '1', '1', '1' }
};

struct Pos
{
    short x,y;
	Pos operator + ( Pos p ) const { return Pos(x+p.x,y+p.y); }
	bool operator < ( Pos p ) const { return ( y==p.y ) ? (x<p.x) : (y<p.y) ; }
	bool operator != ( Pos p ) const { return ( y!=p.y ) || (x!=p.x) ; }
    Pos(short x=0,short y=0) : x(x), y(y) {}
};

bool valid(Pos p) { return p.x>=0 && p.x<MapWidth && p.y>=0 && p.y<MapHeight; }

enum Dir { d_beg, d_up=d_beg, d_rg, d_dn, d_lf, d_end };

Pos deltas[d_end] = { {0,-1}, {+1,0}, {0,+1}, {-1,0} };

Dir& operator ++ ( Dir& d ) { d = (Dir) ( 1+(int)d ) ; return d; }

Dir other(Dir d)
{
	switch(d)
	{
	case d_up: return d_dn;
	case d_rg: return d_lf;
	case d_dn: return d_up;
	case d_lf: return d_rg;
	default: return d_end;
	}
}

struct SearchMapItem
{
	bool traversble;
	bool goal;
	bool visited;
	int cost_here;
	Dir came_from;
	bool paths[d_end];
};

map<Pos,SearchMapItem> search_map;
typedef map<Pos,SearchMapItem>::iterator SMII;

void MakeMap()
{
	search_map.clear();
	Pos p;
	for(p.y=0;p.y<MapHeight;++p.y) for(p.x=0;p.x<MapWidth;++p.x)
	{
		SearchMapItem smi;
		//if(Map[p.y][p.x] == 'D'){
		smi.visited = false;
		smi.cost_here = -1;
		smi.came_from = d_end;
		//}else
		if( Map[p.y][p.x] == 'X' )
		{
			smi.traversble = false;
		}
		else if( Map[p.y][p.x] == 'D' )
		{
			smi.traversble = true;
			smi.goal = true;
		}
		else// if( Map[p.y][p.x] == FLOOR )
		{
			smi.traversble = true;
			smi.goal = false;
			for( Dir d = d_beg; d != d_end; ++d )
			{
				Pos p2 = p + deltas[d];
				smi.paths[d] = valid(p2) && (Map[p2.y][p2.x] != 'X') ;
			}
		}
		search_map[p] = smi;
	}
}

void FindGoalFrom( Pos start )
{
	vector<SMII> found;

	{
		SMII smii = search_map.find(start);

		if(smii==search_map.end()) { cout << "starting outside map\n"; return; }
		if(smii->second.goal) { cout << "already at target\n"; return; }
		if(!smii->second.traversble) { cout << "starting in a wall\n"; return; }

		smii->second.visited = true;
		smii->second.cost_here = 0;
		found.push_back(smii);
	}

	int cost_so_far = 0;
	bool did_find = false;

	while(!did_find)
	{

		vector<SMII> candidates;

		for( SMII smii : found )
		{
			for( Dir d = d_beg; d != d_end; ++d )
			{
				if( ! smii->second.paths[d] ) continue;
				Pos p = smii->first + deltas[d];
				if(!valid(p)) continue;
				SMII cand = search_map.find(p);
				if(cand==search_map.end()) continue;
				if(cand->second.visited) continue;
				cand->second.came_from=d;
				candidates.push_back(cand);
			}
		}

		++cost_so_far;

		if( candidates.empty() ) break;

		for( SMII smii : candidates )
		{
			smii->second.visited = true;
			smii->second.cost_here = cost_so_far;
			found.push_back(smii);
			if( smii->second.goal ) { did_find = true; break; }
		}

	}

	if( ! did_find ) { cout << "no goal reachable\n"; return; }

	SMII pos = found.back();

	vector<Dir> path;

	while( pos->first != start )
	{
		Dir d = pos->second.came_from;
		path.push_back(d);
		Pos p = pos->first + deltas[ other(d) ];
		pos = search_map.find(p);
	}

	for( auto itr = path.rbegin(); itr != path.rend(); ++itr )
	{
		const char* dir_names[] = { "Up", "Right", "Down", "Left" } ;
		cout << "Walk " << dir_names[*itr] << endl;
	}
	cout << "Then you are at goal in total " << to_string(cost_so_far) << " steps" << endl;
}

int main()
{
    MakeMap();

    FindGoalFrom( Pos(2,0) );

    cout << "\ndone\n";
}

dijkstra02.cpp

#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <string>

using namespace std;


#include <sstream>
#include <string>

template <typename T>
std::string to_string(const T& value)
{
    std::ostringstream oss;
    oss << value;

    return oss.str();
}

const int MapWidth = 4, MapHeight = 3;
//       Y pos      X pos
char Map[MapHeight][MapWidth] = {
                 {'X','1','S','3'},
                 {'4','2','X','4'},
                 {'X','1','D','2'},
};

struct Position
{
    short x,y;
	Position operator + ( Position p ) const { return {x+p.x, y+p.y}; }
	bool operator < ( Position p ) const { return ( y==p.y ) ? (x<p.x) : (y<p.y) ; }
	bool operator != ( Position p ) const { return ( y!=p.y ) || (x!=p.x) ; }
    Position(short x=0,short y=0) : x(x), y(y) {}
};

bool valid(Position p) { return p.x >= 0 && p.x < MapWidth && p.y >= 0 && p.y < MapHeight; }

enum Dir { Up, Right, Down, Left, Counts };

Position deltas[Counts] = { {0,-1}, {+1,0}, {0,+1}, {-1,0} };

Dir& operator ++ ( Dir& d ) { d = (Dir) ( 1+(int)d ) ; return d; }

Dir other(Dir d)
{
	switch(d)
	{
	case Up: return Down;
	case Right: return Left;
	case Down: return Up;
	case Left: return Right;
	default: return Counts;
	}
}

struct SearchMapItem
{
	bool traversble;
	bool goal;
	bool visited;
	int cost_here;
	Dir came_from;
	bool paths[Counts];
};

map<Position,SearchMapItem> search_map;
typedef map<Position,SearchMapItem>::iterator SMII;

void MakeMap()
{
	search_map.clear();
	Position p;
	for(p.y=0; p.y< MapHeight; ++p.y)
	{
        for(p.x = 0; p.x < MapWidth; ++p.x)
        {
            SearchMapItem smi;
            //if( Map[p.y][p.x] == 'S')
            {
                smi.visited = false;
                smi.cost_here = -1;
                smi.came_from = Counts;
            }
           // else
            if( Map[p.y][p.x] == 'X' )
            {
                smi.traversble = false;
            }
            else if( Map[p.y][p.x] == 'D' )
            {
                smi.traversble = true;
                smi.goal = true;
            }
            else
            {
                smi.traversble = true;
                smi.goal = false;
                for( Dir d = Dir(0); d != Counts; ++d )
                {
                    Position p2 = p + deltas[d];
                    smi.paths[d] = valid(p2) && (Map[p2.y][p2.x] != 'X') ;
                }
            }
            search_map[p] = smi;
        }
	}
}

void FindGoalFrom( Position start )
{
	vector<SMII> found;

	{
		SMII smii = search_map.find(start);

		if(smii==search_map.end()) { cout << "starting outside map\n"; return; }
		if(smii->second.goal) { cout << "already at target\n"; return; }
		if(!smii->second.traversble) { cout << "starting in a wall\n"; return; }

		smii->second.visited = true;
		smii->second.cost_here = 0;
		found.push_back(smii);
	}

	int cost_so_far = 0;
	bool did_find = false;

	while(!did_find)
	{

		vector<SMII> candidates;

		for( SMII smii : found )
		{
			for( Dir d = Dir(0); d != Counts; ++d )
			{
				if( ! smii->second.paths[d] ) continue;
				Position p = smii->first + deltas[d];
				if(!valid(p)) continue;
				SMII cand = search_map.find(p);
				if(cand==search_map.end()) continue;
				if(cand->second.visited) continue;
				cand->second.came_from=d;
				candidates.push_back(cand);
			}
		}

		++cost_so_far;

		if( candidates.empty() ) break;

		for( SMII smii : candidates )
		{
			smii->second.visited = true;
			smii->second.cost_here = cost_so_far;
			found.push_back(smii);
			if( smii->second.goal ) { did_find = true; break; }
		}

	}

	if( ! did_find ) { cout << "no goal reachable\n"; return; }

	SMII pos = found.back();

	vector<Dir> path;

	while( pos->first != start )
	{
		Dir d = pos->second.came_from;
		path.push_back(d);
		Position p = pos->first + deltas[ other(d) ];
		pos = search_map.find(p);
	}

	for( auto itr = path.rbegin(); itr != path.rend(); ++itr )
	{
		const char* dir_names[] = { "Up", "Right", "Down", "Left" } ;
		cout << "Walk " << dir_names[*itr] << endl;
	}
	cout << "Then you are at goal in total " << to_string(cost_so_far) << " steps" << endl;
}

int main()
{
    MakeMap();

    FindGoalFrom( Position(2,0) );

    cout << "\ndone\n";
}

dijkstra03.cpp

#include <iostream>
#include <map>
#include <vector>
#include <unordered_set>
#include <list>

template<class Item, class Compare = std::less<Item>>
class Heap {
public:
    // implements priority queue data ADT
    void insert(Item* val);
    Item* extract_min();
    void build_min_heap() { for (int i = heapSize_/2 ; i >= 0 ; i--) min_heapify(i); }
    int heapSize() const { return heapSize_; }
    void print() const;
    void adjust_priority(int i);
private:
    void swapIndices(Item* a, Item* b);
    void min_heapify(int i);
    int parent(int i) { return i/2; }
    int left(int i) { return 2*i; }
    int right(int i) { return 2*i+1; }
    int heapSize_ = 0;
    std::vector<Item*> myHeap_;
};

template<class Item, class Compare>
void Heap<Item,Compare>::insert(Item* val)
{
    val->idx_ = heapSize_;
    myHeap_.push_back(val);
    ++heapSize_;
}

template<class Item, class Compare>
void Heap<Item,Compare>::swapIndices(Item* a, Item* b)
{
    int temp = a->idx_;
    a->idx_ = b->idx_;
    b->idx_ = temp;
}

template<class Item, class Compare>
void Heap<Item,Compare>::adjust_priority(int i)
{
    while( i > 0 && myHeap_[parent(i)]->key() > myHeap_[i]->key() )
    {
        swapIndices( myHeap_[i], myHeap_[parent(i)] );
        std::iter_swap( myHeap_.begin()+i, myHeap_.begin()+parent(i) );
        i = parent(i);
    }
}

template<class Item, class Compare>
void Heap<Item,Compare>::min_heapify(int i)
{
    int l = left(i);
    int r = right(i);
    int smallest;
    if( l < heapSize_ && myHeap_[l]->key() < myHeap_[i]->key() ) { smallest = l; }
    else { smallest = i; }
    if( r < heapSize_ && myHeap_[r]->key() < myHeap_[smallest]->key() ) smallest = r;
    if( smallest!=i )
    {
        // swap i with m
        swapIndices( myHeap_[i], myHeap_[smallest] );
        std::iter_swap( myHeap_.begin()+i, myHeap_.begin()+smallest );
        min_heapify(smallest);
    }
}

template<class Item, class Compare>
Item* Heap<Item,Compare>::extract_min()
{
    Item* min = myHeap_[0];
    swapIndices( myHeap_[0], myHeap_[heapSize_-1] );
    std::iter_swap(myHeap_.begin(),myHeap_.begin() + heapSize_-1);
    // run min_heapify on the decremented heap
    --heapSize_;
    min_heapify(0);
    return min;
}



template<class Label, class Edge>
class Graph {
public:
    ~Graph() { for( auto it : nodeMap_) delete it.second; }
    void addNode(const Label& name);
    void deleteNode(const Label& name);
    // adds a directed edge pointing from name1 to name2
    void addEdge(const Label& name1, const Label& name2, Edge w = 1);
    void printNeighbors(const Label& name);
    void Dijkstra(const Label& start);
private:
    class Node;
    class CompareNode;
    bool relax(Node* u, Node* v);
    // returns a pointer to a node given its label
    Node* pointerOf(const Label& name);
    std::map<Label,Node*> nodeMap_;
    // priority queue for Dijkstra
    Heap<Node> Q;
};

template<class Label, class Edge> class
Graph<Label,Edge>::Node {
public:
    Node(const Label& name) : label_(name), Pi_(nullptr), d_(0), idx_(0) { std::cout << "Node '" << name << "' created" << "\n"; }
    ~Node();
    void addOutgoing(Node* p, Edge w) { outgoing_.push_back( {p,w} ); }
    void addIncoming(Node* p) { incoming_.push_back(p); }
    void deleteOutgoing(Node* p);
    // API for priority queue
    Edge key() { return d_; }
    void setkey(Edge key) { d_ = key; }
    const Label& label() const { return label_; }
    // node identifier
    Label label_;
    // incoming and outgoing nodes
    std::list< std::pair<Node*, Edge> > outgoing_;
    std::list<Node*> incoming_;
    // predecessor/distance data structure for Dijkstra
    Node* Pi_;
    Edge d_;
    // position in underlying array
    int idx_;
};

template<class Label, class Edge>
class Graph<Label,Edge>::CompareNode {
public:
    CompareNode(Node* n) : n_(n) {}
    bool operator()(const std::pair<Node*,Edge>& elem) const { return n_ == elem.first; }
private:
    Node* n_;
};

template<class Label, class Edge>
bool Graph<Label,Edge>::relax(Node* u, Node* v)
{
    // find the weight of the node pointing from u to v
    typename std::list< std::pair<Node*, Edge> >::iterator it
            = std::find_if( u->outgoing_.begin(),u->outgoing_.end(),CompareNode(v) );
    if( it != u->outgoing_.end() ) // if there is an edge pointing from u to v
    {
        Edge w = it->second;
        // check relaxation condition
        if(v->d_ > u->d_ + w)
        {
            v->d_ = u->d_ + w;
            v->Pi_ = u;
            return true;
        }
        return false;
    }
    return false;
}

template<class Label, class Edge>
Graph<Label,Edge>::Node::~Node()
{
    // for each incoming node n, remove 'this' pointer from n's list of outgoing
    for ( auto it : incoming_ ) it->deleteOutgoing(this);
    std::cout << "Node '" << label_ << "' destroyed\n";
}

template<class Label, class Edge>
void Graph<Label,Edge>::addNode(const Label& name)
{
    if( ! pointerOf(name) ) // avoids memory leak if name is already there
    {
        Node* n = new Node(name);
        nodeMap_.insert( {name,n} );
    }
}

template<class Label, class Edge>
void Graph<Label,Edge>::deleteNode(const Label& name)
{
    typename std::map<Label,Node*>::iterator it = nodeMap_.find(name);
    if( it != nodeMap_.end() ) delete it->second;
}

template<class Label, class Edge>
void Graph<Label,Edge>::addEdge(const Label& name1,const Label& name2, Edge w)
{
    Node* n1 = pointerOf(name1);
    Node* n2 = pointerOf(name2);
    if( n1 && n2 ) // if name1 and name2 exist
    {
        n1->addOutgoing(n2,w);
        n2->addIncoming(n1);
    }
}

template<class Label, class Edge>
void Graph<Label,Edge>::printNeighbors(const Label& name)
{
    Node* n = pointerOf(name);
    for( auto it : n->outgoing_ ) std::cout << "(" << it.first->label_ << "," << it.second << ")" << " ";
    std::cout << "\n";
}

template<class Label, class Edge>
void Graph<Label,Edge>::Node::deleteOutgoing(Node* n)
{
    typename std::list< std::pair<Node*, Edge> >::iterator it
        = std::find_if(outgoing_.begin(),outgoing_.end(),CompareNode(n));

    if( it != outgoing_.end() ) outgoing_.erase(it);
}

template<class Label, class Edge>
typename Graph<Label,Edge>::Node* Graph<Label,Edge>::pointerOf(const Label& name)
{
    typename std::map<Label,Node*>::iterator it = nodeMap_.find(name);
    if( it != nodeMap_.end() ) { return it->second; }
    else { return nullptr; }
}

template<class Label, class Edge>
void Graph<Label,Edge>::Dijkstra(const Label& start)
{
    for( auto it : Graph::nodeMap_ ) it.second->d_ = std::numeric_limits<Edge>::max();
    // initialize the distance estimate of the starting node to zero
    Node* pstart = pointerOf(start); // maintain pointer for future use
    pstart->d_ = 0;
    // create a set to store processed nodes
    std::unordered_set<Node*> S;
    // insert nodes into priority queue in correct order
    Q.insert(pstart);
    for( auto it : nodeMap_ )
    {
        if(it.second != pstart ) Q.insert(it.second);
    }

    while( Q.heapSize()!=0 ) //
    {
        Node* u = Q.extract_min();
        S.insert( u );
        // for each neighbor v of u, perform relax(u,v)
        for( auto it : u->outgoing_ )
        {
            if( relax( u, it.first ) )
            {
                Q.adjust_priority( it.first->idx_ );
            }
        }
    }
    // print out the shortest path weights
    for( auto it : S ) std::cout << "(" << it->label_ << "," << it->d_ << ")" << " ";
    std::cout << "\n";
}

int main()
{
    std::vector<std::string> nodes = {"a","b","c","d","e","f","g"};
    std::vector< std::pair<std::string,std::string> > edges =
    {
        {"a","b"},{"b","c"},{"c","d"},
        {"b","a"},{"c","b"},{"d","c"},
        {"c","e"},{"e","f"},{"b","f"},
        {"e","c"},{"f","e"},{"f","b"},
        {"f","g"},{"a","g"},
        {"g","f"},{"g","a"}
    };

    std::cout << "\n";
    Graph<std::string,double> myGraph;
    for(auto it : nodes) myGraph.addNode(it);
    for(auto it : edges) myGraph.addEdge(it.first,it.second);
    myGraph.Dijkstra("a");
}

dijkstra04.cpp

#include <set>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <sstream>

// C::B : error stoi is not member of 'std'
unsigned int string_to_int(const std::string& str)
{
    unsigned int value;
    std::stringstream ss(str);
    if (!(ss >> value) || !ss.eof())
    {
        throw std::invalid_argument("Oops\n");
    }
    return value;
}

template<typename N, typename IdType = N>
class Graph
{
    class Node;
    using NodeHolder    = std::set<Node>;
public:
    using NodeId        = IdType;
    using NodeRef       = typename NodeHolder::iterator;
    using Edges         = std::vector<std::pair<NodeRef, int>>;
private:
    class Node
    {
        N data;
        mutable Edges   outedge;
    public:
        Node(N const& data)
            : data(data)
        {}
        void addEdge(NodeRef e, int cost) const
        {
            outedge.emplace_back(e, cost);
        }
        NodeId const& id() const
        {
            return data;
        }
        Edges const& getEdges() const
        {
            return outedge;
        }
        friend bool operator<(Node const& lhs, Node const& rhs)
        {
            return lhs.data < rhs.data;
        }
    };
    NodeHolder   nodes;
public:
    NodeRef addNode(N const& data)
    {
        auto const& result = nodes.emplace(data);
        return result.first;
    }
    NodeRef getRef(N const& data)
    {
        auto const& found = nodes.find(data);
        if(found == nodes.end())
            throw std::runtime_error("Graph::getRef: Key not found!\n");
        return found;
    }
    void addEdge(NodeRef src, NodeRef dst, int cost)
    {
        if (src != nodes.end() && dst != nodes.end()) {
            src->addEdge(dst, cost);
        }
    }
    Edges const& getEdges(N const& node) const
    {
        auto const& found = nodes.find(node);
        if(found == nodes.end())
            throw std::runtime_error("Graph::getEdges: node not found!\n");
        return found;
    }
};

template<typename Graph>
class Dijkstra
{
    //  Graph: The graph type we will traverse
    //     Graph::NodeRef          Type that defines references to the nodes.
    //     Graph::NodeId           A type that uniquely identifies a node.
    //        nodeRef->id()        Gives a unique ID that identifies the node.
    //                             So we don't need to processes it more than once.
    //        nodeRef->getEdges()  returns a container with {NodeRef, Cost}
    using NodeRef = typename Graph::NodeRef;
    using NodeId  = typename Graph::NodeId;
    // Its a tuple really:
    // It is used in a priority queue used by the route algorithm
    //     1:  The node we have reached.
    //     2:  The cost to get to this node.
    //     3:  An ordered list of nodes to get here with this cost.
    struct QueInfo: public std::tuple<NodeRef, int, std::vector<NodeRef>>
    {
        public:
            QueInfo(QueInfo const&) = default;
            QueInfo(NodeRef const& data, int cost, std::vector<NodeRef> const& route)
                : std::tuple<NodeRef, int, std::vector<NodeRef>>(data, cost, route)
            {
                // Add the current node to the end of the route
                std::get<2>(*this).emplace_back(data);
            }
            // Allow QueInfo to be ordered (for the priority queue
            friend bool operator<(QueInfo const& lhs, QueInfo const& rhs)
            {
                return std::get<1>(lhs) > std::get<1>(rhs);
            }
    };

    Graph const&  graph;

public:
    Dijkstra(Graph const& graph)
        : graph(graph)
    {}

    std::vector<NodeRef> route(NodeRef const& src, NodeRef const& dst)
    {
        std::set<NodeId>              found;
        std::priority_queue<QueInfo>  frontier;

        frontier.emplace(src, 0, std::vector<NodeRef>{});

        while(!frontier.empty()) {

            auto next = frontier.top();
            frontier.pop();

            auto const& current = std::get<0>(next);

            if (found.find(current->id()) != found.end()) {
                continue;
            }
            found.emplace(current->id());

            auto const& result = std::get<2>(next);
            if (current == dst) {
                return result;
            }

            for(auto const& loop: current->getEdges()) {
                frontier.emplace(loop.first, std::get<1>(next) + loop.second, result);
            }
        }
        return {};
    }
};

template<typename T>
struct RefPrinter
{
    T const& data;
    RefPrinter(T const& data) : data(data) {}
    friend std::ostream& operator<<(std::ostream& str, RefPrinter const& value)
    {
        return str << "result: " << value.data->id();
    }
};

int main()
{
try{
    using Graph    = Graph<std::string>;
    using Dijkstra = Dijkstra<Graph>;

    Graph graph;
    std::vector<std::string> nodes = {"a","b","c","d","e","f","g"};
    std::vector< std::pair<std::string,std::string> > edges =
    {
        {"a","b"},{"b","c"},{"c","d"},
        {"b","a"},{"c","b"},{"d","c"},
        {"c","e"},{"e","f"},{"b","f"},
        {"e","c"},{"f","e"},{"f","b"},
        {"f","g"},{"a","g"},
        {"g","f"},{"g","a"}
    };

    for(auto const& it : nodes) {
        graph.addNode(it);
    }
    for(auto const& it : edges) {
        graph.addEdge(graph.getRef(it.first), graph.getRef(it.second), 1);
    }

    Dijkstra    dijkstra(graph);

    auto const& result = dijkstra.route(graph.getRef("a"), graph.getRef("g"));
    std::copy(std::begin(result), std::end(result),
              std::ostream_iterator<RefPrinter<Graph::NodeRef>>(std::cout, "\n"));
} catch(std::runtime_error& e)
{
    std::cout << "Exception: " << e.what() << '\n';
    return 1;
}
catch(...)
{
    std::cout << "Unknown Exception!\n";
    return 1;
}
}

dijkstra05.cpp

// all in one
/*
 Sample code from http://www.redblobgames.com/pathfinding/
 Copyright 2014 Red Blob Games <redblobgames@gmail.com>

 Feel free to use this code in your own projects, including commercial projects
 License: Apache v2.0 <http://www.apache.org/licenses/LICENSE-2.0.html>
*/

#include <iostream>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <vector>
#include <utility>
#include <queue>
#include <tuple>
#include <functional>
#include <algorithm>
#include <windows.h>

using std::unordered_map;
using std::unordered_set;
using std::array;
using std::vector;
using std::queue;
using std::priority_queue;
using std::pair;
using std::tuple;
using std::tie;
using std::string;
using std::cout;
using std::cin;
using std::endl;

template<typename L>
struct SimpleGraph {
  typedef L Location;
  typedef typename vector<Location>::iterator iterator;
  unordered_map<Location, vector<Location> > edges;

  inline const vector<Location>  neighbors(Location id) {
    return edges[id];
  }
};

SimpleGraph<char> example_graph {{
    {'A', {'B'}},
    {'B', {'A', 'C', 'D'}},
    {'C', {'A'}},
    {'D', {'E', 'A'}},
    {'E', {'B'}}
  }};

// Helpers for SquareGrid::Location

// When using std::unordered_map<T>, we need to have std::hash<T> or
// provide a custom hash function in the constructor to unordered_map.
// Since I'm using std::unordered_map<tuple<int,int>> I'm defining the
// hash function here. It would be nice if C++ automatically provided
// the hash function for tuple and pair, like Python does. It would
// also be nice if C++ provided something like boost::hash_combine. In
// any case, here's a simple hash function that combines x and y:
namespace std {
  template <>
  struct hash<tuple<int,int> > {
    inline size_t operator()(const tuple<int,int>& location) const {
      int x, y;
      tie (x, y) = location;
      return x * 1812433253 + y;
    }
  };
}

// For debugging it's useful to have an ostream::operator << so that we can write cout << foo
std::basic_iostream<char>::basic_ostream& operator<<(std::basic_iostream<char>::basic_ostream& out, tuple<int,int> loc) {
  int x, y;
  tie (x, y) = loc;
  out << '(' << x << ',' << y << ')';
  return out;
}

// This outputs a grid. Pass in a distances map if you want to print
// the distances, or pass in a point_to map if you want to print
// arrows that point to the parent location, or pass in a path vector
// if you want to draw the path.
template<class Graph>
void draw_grid(const Graph& graph, int field_width=2,
               unordered_map<typename Graph::Location, double>* distances=nullptr,
               unordered_map<typename Graph::Location, typename Graph::Location>* point_to=nullptr,
               vector<typename Graph::Location>* path=nullptr) {
  for (int y = 0; y != graph.height; ++y) {
    for (int x = 0; x != graph.width; ++x) {
      typename Graph::Location id {x, y};
      std::cout << std::left << std::setw(field_width);
      if (graph.walls.count(id)) {
        std::cout << string(field_width, '#');
      } else if (point_to != nullptr && point_to->count(id)) {
        int x2, y2;
        tie (x2, y2) = (*point_to)[id];
        // TODO: how do I get setw to work with utf8?(hex)
        if (x2 == x + 1) { std::cout << "\x1a";}//\u2192 "; }
        else if (x2 == x - 1) { std::cout << "\x1b";}//"\u2190 "; }
        else if (y2 == y + 1) { std::cout << "\x19";}//"\u2193 "; }
        else if (y2 == y - 1) { std::cout << "\x18";}//"\u2191 "; }
        else { std::cout << "*"; }
      } else if (distances != nullptr && distances->count(id)) {
        std::cout << (*distances)[id];
      } else if (path != nullptr && find(path->begin(), path->end(), id) != path->end()) {
        std::cout << '@';
      } else {
        std::cout << '.';
      }
    }
    std::cout << std::endl;
  }
}

struct SquareGrid {
  typedef tuple<int,int> Location;
  static array<Location, 4> DIRS;

  int width, height;
  unordered_set<Location> walls;

  SquareGrid(int width_, int height_)
     : width(width_), height(height_) {}

  inline bool in_bounds(Location id) const {
    int x, y;
    tie (x, y) = id;
    return 0 <= x && x < width && 0 <= y && y < height;
  }

  inline bool passable(Location id) const {
    return !walls.count(id);
  }

  vector<Location> neighbors(Location id) const {
    int x, y, dx, dy;
    tie (x, y) = id;
    vector<Location> results;

    for (auto dir : DIRS) {
      tie (dx, dy) = dir;
      Location next(x + dx, y + dy);
      if (in_bounds(next) && passable(next)) {
        results.push_back(next);
      }
    }

    if ((x + y) % 2 == 0) {
      // aesthetic improvement on square grids
      std::reverse(results.begin(), results.end());
    }

    return results;
  }
};

array<SquareGrid::Location, 4> SquareGrid::DIRS {Location{1, 0}, Location{0, -1}, Location{-1, 0}, Location{0, 1}};

void add_rect(SquareGrid& grid, int x1, int y1, int x2, int y2) {
  for (int x = x1; x < x2; ++x) {
    for (int y = y1; y < y2; ++y) {
      grid.walls.insert(SquareGrid::Location { x, y });
    }
  }
}

SquareGrid make_diagram1() {
  SquareGrid grid(30, 15);
  add_rect(grid, 3, 3, 5, 12);
  add_rect(grid, 13, 4, 15, 15);
  add_rect(grid, 21, 0, 23, 7);
  add_rect(grid, 23, 5, 26, 7);
  return grid;
}

struct GridWithWeights: SquareGrid {
  unordered_set<Location> forests;
  GridWithWeights(int w, int h): SquareGrid(w, h) {}
  double cost(Location from_node, Location to_node) const {
    return forests.count(to_node) ? 5 : 1;
  }
};

GridWithWeights make_diagram4() {
  GridWithWeights grid(10, 10);
  add_rect(grid, 1, 7, 4, 9);
  typedef SquareGrid::Location L;
  grid.forests = unordered_set<SquareGrid::Location> {
    L{3, 4}, L{3, 5}, L{4, 1}, L{4, 2},
    L{4, 3}, L{4, 4}, L{4, 5}, L{4, 6},
    L{4, 7}, L{4, 8}, L{5, 1}, L{5, 2},
    L{5, 3}, L{5, 4}, L{5, 5}, L{5, 6},
    L{5, 7}, L{5, 8}, L{6, 2}, L{6, 3},
    L{6, 4}, L{6, 5}, L{6, 6}, L{6, 7},
    L{7, 3}, L{7, 4}, L{7, 5}
  };
  return grid;
}

template<typename T, typename priority_t>
struct PriorityQueue {
  typedef pair<priority_t, T> PQElement;
  priority_queue<PQElement, vector<PQElement>,
                 std::greater<PQElement>> elements;

  inline bool empty() const { return elements.empty(); }

  inline void put(T item, priority_t priority) {
    elements.emplace(priority, item);
  }

  inline T get() {
    T best_item = elements.top().second;
    elements.pop();
    return best_item;
  }
};

template<typename Graph>
void dijkstra_search
  (const Graph& graph,
   typename Graph::Location start,
   typename Graph::Location goal,
   unordered_map<typename Graph::Location, typename Graph::Location>& came_from,
   unordered_map<typename Graph::Location, double>& cost_so_far)
{
  typedef typename Graph::Location Location;
  PriorityQueue<Location, double> frontier;
  frontier.put(start, 0);

  came_from[start] = start;
  cost_so_far[start] = 0;

  while (!frontier.empty()) {
    auto current = frontier.get();

    if (current == goal) {
      break;
    }

    for (auto next : graph.neighbors(current)) {
      double new_cost = cost_so_far[current] + graph.cost(current, next);
      if (!cost_so_far.count(next) || new_cost < cost_so_far[next]) {
        cost_so_far[next] = new_cost;
        came_from[next] = current;
        frontier.put(next, new_cost);
      }
    }
  }
}


template<typename Location>
vector<Location> reconstruct_path(
   Location start,
   Location goal,
   unordered_map<Location, Location>& came_from
) {
  vector<Location> path;
  Location current = goal;
  path.push_back(current);
  while (current != start) {
    current = came_from[current];
    path.push_back(current);
  }
  std::reverse(path.begin(), path.end());
  return path;
}

inline double heuristic(SquareGrid::Location a, SquareGrid::Location b) {
  int x1, y1, x2, y2;
  tie (x1, y1) = a;
  tie (x2, y2) = b;
  return abs(x1 - x2) + abs(y1 - y2);
}

template<typename Graph>
void a_star_search
  (const Graph& graph,
   typename Graph::Location start,
   typename Graph::Location goal,
   unordered_map<typename Graph::Location, typename Graph::Location>& came_from,
   unordered_map<typename Graph::Location, double>& cost_so_far)
{
  typedef typename Graph::Location Location;
  PriorityQueue<Location, double> frontier;
  frontier.put(start, 0);

  came_from[start] = start;
  cost_so_far[start] = 0;

  while (!frontier.empty()) {
    auto current = frontier.get();

    if (current == goal) {
      break;
    }

    for (auto next : graph.neighbors(current)) {
      double new_cost = cost_so_far[current] + graph.cost(current, next);
      if (!cost_so_far.count(next) || new_cost < cost_so_far[next]) {
        cost_so_far[next] = new_cost;
        double priority = new_cost + heuristic(next, goal);
        frontier.put(next, priority);
        came_from[next] = current;
      }
    }
  }
}

/////////////////////////////////////////////////////////////////////////
template<typename Graph>
void breadth_first_search(Graph graph, typename Graph::Location start) {
  typedef typename Graph::Location Location;
  queue<Location> frontier;
  frontier.push(start);

  unordered_set<Location> visited;
  visited.insert(start);

  while (!frontier.empty()) {
    auto current = frontier.front();
    frontier.pop();

    std::cout << "Visiting " << current << std::endl;
    for (auto next : graph.neighbors(current)) {
      if (!visited.count(next)) {
        frontier.push(next);
        visited.insert(next);
      }
    }
  }
}

template<typename Graph>
unordered_map<typename Graph::Location, typename Graph::Location>
breadth_first_search1(Graph graph, typename Graph::Location start) {
  typedef typename Graph::Location Location;
  queue<Location> frontier;
  frontier.push(start);

  unordered_map<Location, Location> came_from;
  came_from[start] = start;

  while (!frontier.empty()) {
    auto current = frontier.front();
    frontier.pop();

    for (auto next : graph.neighbors(current)) {
      if (!came_from.count(next)) {
        frontier.push(next);
        came_from[next] = current;
      }
    }
  }
  return came_from;
}

template<typename Graph>
unordered_map<typename Graph::Location, typename Graph::Location>
breadth_first_search(const Graph& graph,
                     typename Graph::Location start,
                     typename Graph::Location goal) {
  typedef typename Graph::Location Location;
  queue<Location> frontier;
  frontier.push(start);

  unordered_map<Location, Location> came_from;
  came_from[start] = start;

  while (!frontier.empty()) {
    auto current = frontier.front();
    frontier.pop();

    if (current == goal) {
      break;
    }

    for (auto next : graph.neighbors(current)) {
      if (!came_from.count(next)) {
        frontier.push(next);
        came_from[next] = current;
      }
    }
  }
  return came_from;
}

////////////////////////////////////////////////////////////////
//Dijkstra’s Algorithm

int main()
{
//    UINT oldCodePage = GetConsoleOutputCP();
//    if (!SetConsoleOutputCP(65001)|| !SetConsoleOutputCP(65001)) {
//        cout << "error\n";
//    }
    // breath_first's Algorithm
    breadth_first_search(example_graph, 'A');

    SquareGrid grid = make_diagram1();
    draw_grid(grid, 2);

    auto parents = breadth_first_search1(grid, std::make_tuple(7, 8));
    draw_grid(grid, 2, nullptr, &parents);

    // exit early
    auto parents2 = breadth_first_search(grid, SquareGrid::Location{8, 7}, SquareGrid::Location{17, 2});
    draw_grid(grid, 2, nullptr, &parents2);

    // Dijkstra’s Algorithm
    GridWithWeights gridD = make_diagram4();
    SquareGrid::Location start{1, 4};
    SquareGrid::Location goal{8, 5};
    unordered_map<SquareGrid::Location, SquareGrid::Location> came_from;
    unordered_map<SquareGrid::Location, double> cost_so_far;
    dijkstra_search(gridD, start, goal, came_from, cost_so_far);
    draw_grid(gridD, 2, nullptr, &came_from);
    std::cout << std::endl;
    draw_grid(gridD, 3, &cost_so_far, nullptr);
    std::cout << std::endl;
    vector<SquareGrid::Location> path = reconstruct_path(start, goal, came_from);
    draw_grid(gridD, 3, nullptr, nullptr, &path);

    // aStar's Algorithm
    GridWithWeights gridA = make_diagram4();
    SquareGrid::Location startA{1, 4};
    SquareGrid::Location goalA{8, 5};
    unordered_map<SquareGrid::Location, SquareGrid::Location> came_fromA;
    unordered_map<SquareGrid::Location, double> cost_so_farA;
    a_star_search(gridA, startA, goalA, came_fromA, cost_so_farA);
    draw_grid(gridA, 2, nullptr, &came_fromA);
    std::cout << std::endl;
    draw_grid(gridA, 3, &cost_so_farA, nullptr);
    std::cout << std::endl;
    vector<SquareGrid::Location> pathA = reconstruct_path(startA, goalA, came_fromA);
    draw_grid(gridA, 3, nullptr, nullptr, &pathA);
    //cout << "Hello world!" << endl;

   // SetConsoleOutputCP(oldCodePage);
    return 0;
}