Mace C++ Graph Library 1.0
The fast and flexible graph library for C++. Developed by Matthias Mace H├Ądrich.
Public Member Functions | Private Member Functions | Private Attributes
dijkstra Class Reference

Dijkstra shortest path algorithm. More...

#include <dijkstra.h>

List of all members.

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.
vertexget_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.
graphm_graph
 This is the graph the algorithm will operate on.
vertexm_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.

Returns:
True if something has been inserted into the maps, false if maps are empty.

Definition at line 30 of file dijkstra.cpp.

bool dijkstra::remove_vertex_from_queue ( vertex p_vertex) [private]

Remove a vertex from the queue of not visited vertices.

Returns:
True if removal was successful, false if not.

Definition at line 128 of file dijkstra.cpp.

void dijkstra::update_distance ( vertex p_current,
edge p_successor 
) [private]

Update the distance from the start vertex to the successor currently treated.

Definition at line 174 of file dijkstra.cpp.

bool dijkstra::vertex_not_visited ( vertex p_vertex) [private]

Check if vertex hasn't been visited yet.

This function checks whether p_vertex is contained in queue.

Returns:
True if vertex is contained in queue, false if not.

Definition at line 154 of file dijkstra.cpp.


Member Data Documentation

This is the map that stores the distance from the start vertex to the given vertex in the map.

Definition at line 45 of file dijkstra.h.

dijkstra::m_graph [private]

This is the graph the algorithm will operate on.

Definition at line 63 of file dijkstra.h.

dijkstra::m_start [private]

This is the start vertex where the search for the shortest paths will begin.

Definition at line 69 of file dijkstra.h.

dijkstra::pred_map [private]

This is the map that stores the predecessor of every vertex that has been visited.

Definition at line 51 of file dijkstra.h.

dijkstra::queue [private]

This is the vector that stores all vertices that haven't been visited yet.

Definition at line 57 of file dijkstra.h.


The documentation for this class was generated from the following files:
 All Classes Files Functions Variables Defines