Dijkstra shortest path algorithm. More...

#include <dijkstra.h>

Public Member Functions
DLL	dijkstra (graph p_graph, vertex p_start)
	The constructor.
DLL std::list< vertex * >	get_shortest_path_to (vertex *p_target_vertex)
	Get the shortest path from the start vertex to `p_target_vertex`.
DLL void	get_shortest_path_output (vertex *p_target_vertex, std::ostream &os)
	Get the shortest path from the start vertex to `p_target_vertex` and send the path to an output stream `os`.
Private Member Functions
bool	initialize ()
	Initialize processing.
void	execute ()
	Start the execution of the path finding.
vertex *	get_vertex_with_shortest_distance ()
	Get the vertex in `queue` with the shortest distance from the start vertex.
bool	remove_vertex_from_queue (vertex *p_vertex)
	Remove a vertex from the queue of not visited vertices.
bool	vertex_not_visited (vertex *p_vertex)
	Check if vertex hasn't been visited yet.
void	update_distance (vertex p_current, edge p_successor)
	Update the distance from the start vertex to the successor currently treated.
Private Attributes
std::map< vertex *, int >	distance_map
	This is the map that stores the distance from the start vertex to the given vertex in the map.
std::map< vertex , vertex >	pred_map
	This is the map that stores the predecessor of every vertex that has been visited.
std::vector< vertex * >	queue
	This is the vector that stores all vertices that haven't been visited yet.
graph *	m_graph
	This is the graph the algorithm will operate on.
vertex *	m_start
	This is the start vertex where the search for the shortest paths will begin.

Detailed Description

Dijkstra shortest path algorithm.

This class provides the algorithm to find the shortest path from one vertex to another.
It follows the single-source shortest path pattern, which means that it calculates the shortest path from a start vertex to every other vertex in the graph.
The call of dijkstra() already calculates all shortest paths. And the shortest path to a vertex from the given start vertex is not returned until the call of get_shortest_path_to( vertex* p_vertex ).
Calling shortest_path_output( vertex* p_target_vertex, std::ostream& os ) sends the shortest path to a given output stream.

Note:: This class uses the macro INT_MAX from the C math library to flag a value as infinite.

Definition at line 33 of file dijkstra.h.

Constructor & Destructor Documentation

dijkstra::dijkstra	(	graph *	p_graph,
		vertex *	p_start
	)

The constructor.

Definition at line 8 of file dijkstra.cpp.

Member Function Documentation

void dijkstra::execute ( ) [private]

Start the execution of the path finding.

This starts the processes which are necessary to find the shortest path from one vertex to another.

Definition at line 64 of file dijkstra.cpp.

void dijkstra::get_shortest_path_output	(	vertex *	p_target_vertex,
		std::ostream &	os
	)

Get the shortest path from the start vertex to p_target_vertex and send the path to an output stream os.

This function calls get_shortest_path_to( vertex* p_target_vertex ) and provides output to an output stream like std::cout or a file.

Definition at line 223 of file dijkstra.cpp.

std::list< vertex * > dijkstra::get_shortest_path_to ( vertex * p_target_vertex )

Get the shortest path from the start vertex to p_target_vertex.

This returns the shortest path to the vertex p_target_vertex, beginning at the start vertex. When this function is called, all shortest paths have already been calculated.

Returns:: The path from start to target vertex as a list, sorted in sequential order.

Note:: Instead of returning a std::list it is also possible to send the output directly to an output stream by calling get_shortest_path_output( vertex* p_target_vertex, std::ostream& os ).

Definition at line 196 of file dijkstra.cpp.

vertex * dijkstra::get_vertex_with_shortest_distance ( ) [private]

Get the vertex in queue with the shortest distance from the start vertex.

Returns:: A pointer to the vertex in queue with the shortest distance from the start vertex.

Definition at line 102 of file dijkstra.cpp.

bool dijkstra::initialize ( ) [private]

Initialize processing.

This initializes the maps containing the distance from start to each vertex (distance) and the predecessor of each vertex (pred).
The distance of each vertex is initialized with the value INT_MAX to represent infinity as an invalid value.
The predessor of each vertex is initialized with NULL.