Dijkstra's shortest path algorithm. More...

#include <ahFunction.H>
#include <ah-errors.H>
#include <archeap.H>
#include <tpl_find_path.H>
#include <tpl_agraph.H>
#include <shortest_path_common.H>

Include dependency graph for Dijkstra.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >
	Spanning tree calculation of all shortest paths from a given node according to Dijkstra's algorithm. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Macros
#define	DNassert(p) (static_cast<Node_Info*>(NODE_COOKIE(p)))

#define	TREENODE(p) (static_cast<Tree_Node_Info*>(NODE_COOKIE(p))->tree_node)

#define	ACC(p) (DNassert(p)->dist)

#define	HEAPNODE(p) (DNassert(p)->heap_node)

#define	PARENT(p) (DNassert(p)->ret_node)

#define	DAassert(p) (static_cast<Arc_Info*>(ARC_COOKIE(p)))

#define	ARC_DIST(p) (Distance()(p))

#define	TREEARC(p) (static_cast<Tree_Arc_Info*>(ARC_COOKIE(p))->tree_arc)

#define	POT(p) (DAassert(p)->pot)

Detailed Description

Dijkstra's shortest path algorithm.

Implements Dijkstra's algorithm for finding shortest paths from a source vertex to all other vertices in a weighted graph with non-negative edge weights. Uses binary heap for O((V+E)log V).

Author: Leandro Rabindranath León

Definition in file Dijkstra.H.

Macro Definition Documentation

◆ ACC

#define ACC ( p ) (DNassert(p)->dist)

Definition at line 121 of file Dijkstra.H.

◆ ARC_DIST

#define ARC_DIST ( p ) (Distance()(p))

Definition at line 125 of file Dijkstra.H.

◆ DAassert

#define DAassert ( p ) (static_cast<Arc_Info*>(ARC_COOKIE(p)))

Definition at line 124 of file Dijkstra.H.

◆ DNassert

#define DNassert ( p ) (static_cast<Node_Info*>(NODE_COOKIE(p)))

Definition at line 119 of file Dijkstra.H.

◆ HEAPNODE

#define HEAPNODE ( p ) (DNassert(p)->heap_node)

Definition at line 122 of file Dijkstra.H.

◆ PARENT

#define PARENT ( p ) (DNassert(p)->ret_node)

Definition at line 123 of file Dijkstra.H.

◆ POT

#define POT ( p ) (DAassert(p)->pot)

Definition at line 127 of file Dijkstra.H.

◆ TREEARC

#define TREEARC ( p ) (static_cast<Tree_Arc_Info*>(ARC_COOKIE(p))->tree_arc)

Definition at line 126 of file Dijkstra.H.

◆ TREENODE

#define TREENODE ( p ) (static_cast<Tree_Node_Info*>(NODE_COOKIE(p))->tree_node)

Definition at line 120 of file Dijkstra.H.

Classes

Namespaces

Macros