DijkstraShortestPathsAlgorithm

class DijkstraShortestPathsAlgorithm

Bases: Algorithm[Graph | DiGraph, GraphSize, ShortestPathsGraph]

Dijkstra’s shortest path(s) algorithm.

__init__()

Methods

__init__()
get_worst_case_arguments(input_size)	Generate a graph with input_size.nodes nodes and input_size.edges edges and find the shortest paths to all nodes in the graph from the root.
increment_n_ops([increment])	Convenience method to increment n_ops count of the given complexity object.
reset_n_ops()	Convenience method to reset n_ops count of the given complexity object.
run_algorithm(input_instance[, ...])	Run function of Dijkstra's uni-directional shortest path(s) algorithm.

Attributes

algorithm_family	rtype: AlgorithmFamily
algorithm_properties	rtype: AlgorithmProperties
average_case_time_complexity	rtype: str
best_case_description	rtype: str
best_case_time_complexity	rtype: str
is_deterministic	rtype: bool
n_ops	rtype: int
name	rtype: str
space_complexity	rtype: str
worst_case_description	rtype: str
worst_case_time_complexity	rtype: str

property algorithm_family: AlgorithmFamily

Return type:

AlgorithmFamily

property algorithm_properties: AlgorithmProperties

Return type:

AlgorithmProperties

property average_case_time_complexity: str

Return type:

str

property best_case_description: str

Return type:

str

property best_case_time_complexity: str

Return type:

str

get_worst_case_arguments(input_size)

Generate a graph with input_size.nodes nodes and input_size.edges edges and find the shortest paths to all nodes in the graph from the root. The graph instance starts as a star graph, sequentially adding new star roots until desired number of edges is reached or until the graph is fully connected.

Parameters:

input_size (GraphSize) – Tuple of n_nodes, n_edges with desired graph size.

Returns:

run_algorithm_kwargs – A dictionary with the created graph as ‘input_instance’ value, ‘source’ as the first node and ‘target’ as NoNode() object.

Return type:

dict[str, Any]

increment_n_ops(increment=1)

Convenience method to increment n_ops count of the given complexity object.

Return type:

None

property is_deterministic: bool

Return type:

bool

property n_ops: int

Return type:

int

property name: str

Return type:

str

reset_n_ops()

Convenience method to reset n_ops count of the given complexity object.

Return type:

None

run_algorithm(input_instance, verbosity_level=0, source=NoNode, target=NoNode, fill_weight_value=None, *args, **kwargs)

Run function of Dijkstra’s uni-directional shortest path(s) algorithm.

Parameters:

• input_instance (Graph | DiGraph) – Graph in which to run the search.

• verbosity_level (int (default 0)) – Select the amount of information to print throughout run of the algorithm. One of 0, 1, 2 with 0 referring to no printing, 1 leading to print the shortest path traversal graph at the end and 2 meaning also print the shortest path traversal graph after every expanded node.

• source (Node | NoNode (default NoNode())) – Root node to find the shortest path(s) from. If not given, shortest paths from all nodes are found.

• target (Node | NoNode (default NoNode())) – Target node to find the shortest path(s) to. If not given, shortest paths to all nodes are found.

• fill_weight_value (Optional[float | int] (default None)) – If given and None weight is encountered, fill the None with this value. Otherwise, an error will be raised.

• *args (Any) – Additional arguments passed to the algorithm.

• **kwargs (Any) – Additional keyword arguments passed to the algorithm.

Returns:

result – Returns True in the first index if the shortest path to target was found or if no target was specified. Also returns a ShortestPathsGraph object carrying the respective path lengths and predecessor and capable of reconstructing the path.

Return type:

tuple[bool, ShortestPathsGraph]

property space_complexity: str

Return type:

str

property worst_case_description: str

Return type:

str

property worst_case_time_complexity: str

Return type:

str