1

##### C/C++ & Visual C++ / Re: Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...

« Last post by**David**on

*November 22, 2018, 05:26:44 AM*»

This C++ Shortest Path demo uses a heap as a priority queue ... (Instead of set and map as used in C++ version above.)

Code: [Select]

`// dijkstra_shortest_path_via_min_heap.cpp // // 2018-11-21 //`

// This example uses a MIN HEAP as a MIN PRIORITY QUEUE //

#include <iostream>

#include <sstream>

#include <string>

#include <vector>

#include <list>

#include <limits> // for numeric_limits

#include <algorithm> // re. make_heap(...), pop_heap(...), // renove(...) //

using std::vector;

using std::list;

// utility forward declaration /////////////////////////////////////

template< typename T >

T takeIn( const std::string& msg, const T& min, const T& max );

////////////////////////////////////////////////////////////////////

const double INF = std::numeric_limits< double >::infinity();

struct Edge

{

size_t target;

double distance;

Edge( size_t t, double d ) : target(t), distance(d) {}

};

typedef vector< vector< Edge > > adj_vec_t;

typedef std::pair< size_t, double > pair_t;

typedef vector< std::string > place_vec_t;

struct MyMinCmp

{

bool operator () ( const pair_t& a, const pair_t& b )

{

return b.second < a.second ;

}

} ;

void dijkstraPaths( int source,

const adj_vec_t& adj_vec,

vector< double >& min_distance,

vector< int >& previous )

{

size_t n = adj_vec.size();

min_distance.clear();

min_distance.resize( n, INF );

min_distance[source] = 0;

previous.clear();

previous.resize( n, -1 );

vector< pair_t > vertex_queue;

vertex_queue.push_back( pair_t( source, min_distance[source] ) );

while( !vertex_queue.empty() )

{

size_t u = vertex_queue.front().first;

double dist_first = vertex_queue.front().second;

pop_heap( vertex_queue.begin(), vertex_queue.end(), MyMinCmp() );

vertex_queue.pop_back();

// Visit each edge adjacent to u //

const vector< Edge > &edges = adj_vec[u];

vector< Edge >::const_iterator it = edges.begin();

for ( ; it != edges.end(); ++ it )

{

double through_u = dist_first + it->distance;

size_t v = it->target;

if( through_u < min_distance[v] )

{

pair_t pr = pair_t( v, min_distance[v] );

// THIS BLOCK OF code may be faster RUNNING than 'remove' below ?? //

vector< pair_t >::iterator itt = std::find(

vertex_queue.begin(), vertex_queue.end(), pr );

if (itt != vertex_queue.end() )

{

// swap the one to be removed with the last element

// and remove the item at the end of the container

// to prevent moving all items after '5' by one

std::swap( *itt, vertex_queue.back() );

vertex_queue.pop_back();

}

//std::remove( vertex_queue.begin(), vertex_queue.end(), pr );

////////////////////////////////////////////////////

min_distance[v] = through_u;

previous[v] = u;

vertex_queue.push_back( pair_t( v, min_distance[v] ) );

make_heap( vertex_queue.begin(), vertex_queue.end(), MyMinCmp() );

}

}

}

}

list<int> getShortestPath( int vertex, const vector< int >& previous )

{

list< int > path;

for ( ; vertex != -1; vertex = previous[vertex])

path.push_front(vertex);

return path;

}

void loadAdjList( adj_vec_t& adjacency_list )

{

// NOTE! insert edges both ways for undirected graphs //

adjacency_list[0].push_back(Edge(1, 7));

adjacency_list[1].push_back(Edge(0, 7));

adjacency_list[0].push_back(Edge(2, 9));

adjacency_list[2].push_back(Edge(0, 9));

adjacency_list[0].push_back(Edge(5, 12));

adjacency_list[5].push_back(Edge(0, 12));

adjacency_list[1].push_back(Edge(2, 10));

adjacency_list[2].push_back(Edge(1, 10));

adjacency_list[1].push_back(Edge(3, 13));

adjacency_list[3].push_back(Edge(1, 13));

adjacency_list[2].push_back(Edge(3, 11));

adjacency_list[3].push_back(Edge(2, 11));

adjacency_list[2].push_back(Edge(5, 2));

adjacency_list[5].push_back(Edge(2, 2));

adjacency_list[3].push_back(Edge(4, 6));

adjacency_list[4].push_back(Edge(3, 6));

adjacency_list[4].push_back(Edge(5, 9));

adjacency_list[5].push_back(Edge(4, 9));

}

void showPlaces( const place_vec_t& places )

{

for( size_t i = 0; i < places.size(); ++ i )

std::cout << i << "->" << places[i] << '\n';

}

int main()

{

place_vec_t places;

for( size_t i = 0; i < 6; ++ i )

{

std::ostringstream oss;

oss << i;

places.push_back( "Town_" + oss.str() );

}

adj_vec_t adjacency_list(6);

loadAdjList( adjacency_list );

size_t n = adjacency_list.size();

std::stringstream ss;

ss << n-1;

std::string topStr = ss.str();

// these get initialed inside function dijkstraPaths called below

vector< double > min_distance;

vector< int > previous;

////////////////////////////////////////////////////////////////

while( true )

{

showPlaces( places );

size_t start = takeIn< int>( "Enter place to start (0.." +

topStr + "): ", 0, n-1 );

size_t stop = takeIn< int>( "Enter place to stop (0.." +

topStr + "): ", 0, n-1 );

dijkstraPaths( start, adjacency_list, min_distance, previous );

std::cout << "Distance from " << start << " to " << stop << ": "

<< min_distance[stop] << std::endl;

list< int > path = getShortestPath( stop, previous );

std::cout << "Path : ";

list< int >::const_iterator it = path.begin();

for( ; it != path.end(); ++ it )

std::cout << *it << "->" << places[*it] << " ";

std::cout << std::endl;

std::cout << "More (y/n) ? ";

std::string reply;

getline( std::cin, reply );

if( reply.size() && (reply[0] == 'n' || reply[0] == 'N') )

break;

}

std::cout << "Ok ... exiting ... \nPress 'Enter' to continue/exit ... ";

std::cin.get();

return 0;

}

////////////////////////////////////////////////////////////////////

// definition utility //////////////////////////////////////////////

////////////////////////////////////////////////////////////////////

template< typename T >

T takeIn( const std::string& msg, const T& min, const T& max )

{

while( true )

{

std::cout << msg;

std::string s, tmp;

getline( std::cin, s );

std::istringstream iss( s );

T val;

if( iss >> val && !(iss >> tmp) && val >= min && val <= max )

return val;

// else if reach here ... nOT in valid range //

std::cout << "Only single values in range "

<< min << ".." << max << " are valid here.\n";

}

}