Shortest Path Solver

struct Label

Represents a label in the shortest path computation.

Fields

• value::Float64: The cost to reach the node this label is associated with.
• entering_arc::Arc: The arc through which this node was reached.
• min_hops::Int: The minimum number of arcs required to generate this label.

mutable struct ShortestPathGenerator

A structure to accelerate the shortest path computation in networks by reusing a precomputed topologically sorted list of arcs and updating the solution object across calls.

Storing the pre-sorted list of arcs is particularly beneficial when shortest path computations are frequently repeated with varying costs, as in the pricing solution of column generation for large-scale problems.

Fields

• top_sorted_arc_list::Vector{Arc}: List of arcs already sorted by topological order.
• source::Vertex: Source vertex for the shortest path computation.
• sink::Vertex: Sink (destination) vertex for the shortest path computation.
• solution::ShortestPathSolution: Reusable object that holds the current shortest path solution. Reusing the solution object avoids inneficiencies due to memory allocation in huge problems.

mutable struct ShortestPathSolution

Stores the state necessary for representing a set of solutions of a shortest path computation.

Fields

• forward_vertex_to_label::IndexedMap{Vertex,Label}: Mapping from vertices to labels for forward search from source to each vertex.
• backward_vertex_to_label::IndexedMap{Vertex,Label}: Mapping from vertices to labels for backward search from sink to each vertex.
• arc_to_cost::IndexedMap{Arc,Float64}: Mapping from arcs to their associated costs.
• is_hyper_graph::Bool: Flag indicating if the solution is for a hypergraph. In case this is true, no backward computation has been done.

Constructor

• ShortestPathSolution(network::Network): Initializes the solution with default labels and inf costs for a given network.

build_shortest_path_generator(network::Network, source::Vertex, sink::Vertex) -> ShortestPathGenerator

Constructs a ShortestPathGenerator instance by creating a topologically sorted list of arcs from the network and initializing an empty shortest path solution.

generate_shortest_path(network::Network, arc_to_cost::AbstractDict; solver::ShortestPathGenerator) -> ShortestPathSolution

Generates the shortest path solution for a given network using a specific ShortestPathGenerator.

Returns

• ShortestPathSolution: The shortest path solution found by the solver.

generate_shortest_path(network::Network, source::Vertex, sink::Vertex, arc_to_cost::AbstractDict) -> ShortestPathSolution

Generates the shortest path solution for a given network from a source to a sink, using specific arc costs. Builds a ShortestPathGenerator internally.

Returns

• ShortestPathSolution: The shortest path solution found by the solver.

get_min_unit_flow_cost(solution::ShortestPathSolution, arc::Arc) -> Float64

Calculate the minimum flow cost in a path where the flow on arc is one unit. This function is not compatible with hyper-graphs.

Returns

• Float64: The minimum unit flow cost for the specified arc.

get_min_unit_flow_path(solution::ShortestPathSolution, arc::Arc) -> Path

Obtain the path with the minimum unit flow cost for a given arc. This function does not support hyper-graphs and will throw an error if used in such context.

Returns

• Path: The path corresponding to the minimum unit flow cost of the arc.

get_optimal_path(solution::ShortestPathSolution, sink::Vertex) -> Path

Retrieve the optimal path from the source to the specified sink vertex using the shortest path solution data.

get_optimal_value_from_source(solution::ShortestPathSolution, vertex::Vertex) -> Float64

Return the optimal value (cost) of reaching a specified vertex from the source vertex using the shortest path solution data.