Mace C++ Graph Library 1.0
The fast and flexible graph library for C++. Developed by Matthias
Mace Hädrich. |

dijkstra Class Reference

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. |

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.

The constructor.

Definition at line 8 of file dijkstra.cpp.

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.

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.

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.

dijkstra::distance_map` [private]` |

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:

Generated on Wed Jun 8 2011 09:45:28 for Mace C++ Graph Library by 1.7.4