An Efficient Algorithm for the Quickest Path Reliability Problem

• In a multistate flow network, quickest-path reliability concerns whether a demand can traverse a single minimal path within a time limit, where transmission time depends on total lead time and bottleneck capacity.Source: §2 · pp. 1–2
• Exact procedures may require minimal-path enumeration, whose count can grow exponentially, while incremental searches may still extend partial paths whose infeasibility becomes apparent only near the destination.Source: §2 · p. 2
• Generating lower boundary vectors is only one step in exact reliability evaluation, because their overlapping upper-state events still require an exact union-probability calculation.Source: §2 · p. 2
• Budget-constrained methods also require the complete minimal-path collection, and node–child-matrix pruning based mainly on consumed resources can retain prefixes with no feasible completion.Source: §2 · p. 3
• Destination-based lower bounds estimate the additional lead time and cost required to reach the destination, and capacity-filtered subnetworks strengthen feasibility tests using attainable bottleneck capacity.Source: §2 · p. 3
• The exact resource-aware look-ahead algorithm generates the complete set of (d, T, b) lower boundary vectors without prior minimal-path enumeration or duplicate solutions, with safety and correctness established formally.Source: §2 · p. 4

3.1. Network Model and Notation

• The network has source node 1 and destination node n, with arc capacities represented by random variables and demand, time limit, and budget as problem parameters.The demand and time limit are positive integers, and the budget is nonnegative.Source: §3.1 · pp. 4–5

3.2. Assumptions

• The model assumes discrete, independent arc capacities with known distributions, deterministic nonnegative lead times and costs, and transmission of all flow along a single path.The capacity-independence assumption is needed for the probability calculations, but not for boundary-vector generation.Source: §3.2 · pp. 5–6

3.3. Transmission Time and Feasible Paths

• A path’s transmission time depends on both its lead time and bottleneck capacity, while feasibility also requires meeting the budget and capacity threshold.The path-specific attributes separate from the current state: lead time, cost, and required capacity are path-dependent, while realized bottleneck capacity depends on arc states.Source: §3.3 · pp. 6–7

3.4. Boundary State Vectors

• Every lower boundary vector corresponds to a potentially feasible minimal path, and the resulting path vector is itself a lower boundary vector.This characterization underlies the algorithm’s search over relevant paths rather than prior enumeration of all minimal paths.Source: §3.4 · pp. 8–9
• The algorithm constructs only potentially relevant paths and prunes a partial path when look-ahead conditions establish that it cannot be completed feasibly.This avoids requiring all minimal paths to be generated in advance.Source: §3.4 · p. 9

3.5. Reliability Calculation from Boundary Vectors

• The successful-state set is represented by upper-state events generated from its lower boundary vectors, whose probabilities must be combined because the events can overlap.The paper lists inclusion–exclusion and other exact union-probability procedures as evaluation options.Source: §3.5 · pp. 9–10
• The direct inclusion–exclusion expression can have a number of terms that grows exponentially with the number of lower boundary vectors.Other exact procedures named include disjoint products, binary decision diagrams, and recursive factoring.Source: §3.5 · p. 10

4.1. Motivation and Limitation of the Existing NCM Algorithm

• The existing NCM algorithm checks resources already consumed, so it may expand partial paths that cannot meet destination requirements.Such paths can generate many unnecessary descendants before their infeasibility becomes evident.Source: §4.1 · pp. 10–11

4. The Proposed Resource-Aware Look-Ahead Algorithm

• Admissible lower bounds on remaining resources discard a partial path only when every possible continuation is infeasible.The tests do not prescribe a particular suffix or reject a path merely because one chosen shortest path fails.Source: §4.1 · p. 11

4.2. Basic Destination-Based Bounds

• Shortest-lead-time, least-cost, and widest-capacity tests provide inexpensive basic bounds, but may use different continuations.These unrestricted tests are deliberately optimistic; stronger bounds incorporate required capacity into the underlying networks.Source: §4.2 · pp. 12–13

4.3. Capacity-Filtered Networks

• The method forms distinct positive maximum-capacity levels and, for each level λ, a network containing arcs with maximum capacity at least λ.Every path in that filtered network can potentially provide a bottleneck capacity of at least λ.Source: §4.3 · p. 13
• Within each filtered network, the algorithm computes minimum remaining lead time and unit transmission cost from each node to the destination.These are separate lower bounds and need not be attained by the same path.Source: §4.3 · p. 13
• Reverse-network shortest-path computations obtain the filtered bounds; nonnegative lead times and costs permit Dijkstra’s algorithm.Allowing a bound-producing path to revisit a node in the partial path may weaken the bound but does not invalidate it.Source: §4.3 · p. 13

4.4. Capacity-Aware Look-Ahead Results

• For each possible bottleneck level, filtered lead-time and cost bounds test whether the partial path can meet time and budget limits while supporting that capacity.If no admissible level remains, no potentially feasible path can contain the partial path as a prefix.Source: §4.4 · pp. 13–14
• Passing the capacity-aware test is necessary but not sufficient for a feasible completion, because the optimistic lead-time and cost suffixes may differ.The bounds may also allow suffixes that revisit nodes already in the partial path; this optimism keeps the pruning rule safe.Source: §4.4 · p. 14

4.5. Optional Cost–Time Coupled Bound

• An optional nonnegative weighted bound can strengthen pruning by coupling lead time and cost without exact resource-constrained shortest-path calculations.The multiplier set trades preprocessing effort against pruning strength; exact coupled calculations may be costly, while omitting the enhancement leaves correctness unchanged.Source: §4.5 · p. 15

4.6. Network Preprocessing and Reduction

• Forward and backward reachability searches remove nodes and arcs that do not lie on any source–destination path.In a directed network, retained nodes must be reachable from the source and able to reach the destination.Source: §4.6 · p. 16
• The algorithm computes basic bounds and capacity-filtered lead-time and cost bounds before enumeration, with coupled bounds added when that optional test is active.If the initial partial path fails the basic test, the instance is infeasible.Source: §4.6 · p. 16
• Source- and destination-based filtered distances can identify arcs that cannot lie on any potentially feasible path.The reduction remains safe when bound-producing paths overlap or repeat nodes, since that makes the bounds more optimistic.Source: §4.6 · p. 16
• The arc-reduction test can run once using original filtered-network distances; repeating it after removals is exact but adds computational cost.The additional cost should be evaluated experimentally.Source: §4.6 · p. 16

4.7. The Proposed Algorithm

• RALA combines preprocessing with depth-first enumeration, using an arc-indexed adjacency list to access each candidate arc’s lead time, cost, and maximum capacity.The NCM representation is also supported, and both representations generate the same search tree.Source: §4.7 · p. 17
• For each partial path, RALA tracks its node sequence, accumulated lead time and cost, bottleneck capacity, and visited nodes.The visited-node array prevents repeated nodes and ensures each constructed source–destination path is minimal.Source: §4.7 · p. 17
• RALA-B uses the basic tests, RALA-C adds a capacity-aware test, and optional coupled mode further strengthens RALA-C.The algorithm also supports an optional arc-reduction phase; in RALA-C and coupled mode, capacity levels above the current bottleneck can be skipped.Source: §4.7 · p. 17

4.8. Correctness Results

• Every state vector generated by any RALA mode is a (d, T, b) lower boundary vector.A vector is constructed only after reaching the destination and checking the path’s time, cost, and capacity feasibility conditions.Source: §4.8 · pp. 17, 20
• No mode generates duplicate lower boundary vectors: each simple path is generated at most once, and distinct minimal paths yield different state vectors.The positive demand makes the positive components identify the path’s arcs.Source: §4.8 · p. 20
• Every mode generates every vector in Ψmin_{d,T,b}, because a feasible path cannot have a prefix discarded by the admissible pruning tests.The optional coupled bound preserves the required capacity level, and optional arc reduction does not remove an arc on the path.Source: §4.8 · p. 20

4.9. Complexity Analysis

• Basic destination-based shortest-path values can be computed in O(m + n log n) time using adjacency lists and heap-based implementations.The experiments therefore report search counts, pruning counts, preprocessing time, enumeration time, and total running time to assess practical performance.Source: §4.9 · pp. 21–22
• RALA’s enumeration is output-sensitive: it examines outgoing arcs at invoked partial-path states and explicitly constructs each output vector in O(m) time.The cited complexity expression accounts for the number of invoked states and the σ output vectors.Source: §4.9 · p. 21
• The number of partial paths examined may be exponential when a network has exponentially many simple paths and lower boundary vectors.This worst-case behavior is unavoidable for exact enumeration when the output itself is exponential.Source: §4.9 · p. 22

5. Illustrative Example

• The example illustrates the algorithm’s main steps on a small benchmark network, from calculating capacity-filtered look-ahead information to using the resulting vectors for reliability.The optional cost–time coupled bound and arc-reduction phase are not activated.Source: §5 · p. 22

5.1. Benchmark Network and Input Data

• The benchmark has five nodes, with node 1 as source and node 5 as destination; it uses demand 7, time limit 9, and budget 63.The example disables the optional coupled bound and arc-reduction phase to highlight the pruning conditions.Source: §5 · p. 22, §5.1 · p. 23

5.2. Precomputed Look-Ahead Tables

• Capacity-filtered bounds are computed on subnetworks retaining arcs whose maximum capacity meets each threshold, with infinite entries indicating unreachable destinations.The shortest lead-time and least-cost values are lower bounds and may come from different paths.Source: §5.2 · pp. 23–24, Table 1 · p. 24

5.3. Step-by-Step Execution

• RALA reaches the destination through two potentially feasible paths out of nine simple paths, eliminating four partial paths before the destination.The descendants of those eliminated partial paths are not constructed.Source: §5.3 · p. 26

5.4. Final State Vectors and Reliability

• Under independent, uniform arc-capacity assumptions, the example calculates exact quickest-path reliability from the generated lower boundary vectors.The uniform probabilities keep the probability calculation transparent; boundary-vector generation does not depend on those probabilities.Source: §5.1 · p. 23, §5.4 · p. 27

6. Concluding Remarks

• Destination-based look-ahead uses shortest-lead-time, least-cost, and widest-capacity information about the remaining network to identify partial paths that cannot lead to feasible solutions.The approach considers both resources already consumed and resources necessarily required to reach the destination.Source: §6 · p. 28
• RALA-B applies basic lead-time and cost bounds, while RALA-C strengthens pruning with capacity-filtered subnetworks that account for capacity, transmission time, and cost together.A cost–time coupled condition and iterative arc reduction are optional additional pruning mechanisms.Source: §6 · p. 28
• The algorithms safely generate every (d, T, b) lower boundary vector without duplicates or requiring the complete collection of minimal paths as input.Every eliminated partial path has no extension satisfying demand, time, and budget simultaneously.Source: §6 · p. 28
• The output-sensitive complexity analysis separates preprocessing, partial-path examination, and construction of the final state vectors.Source: §6 · p. 28
• Boundary-vector generation is distinct from reliability evaluation, which can use any suitable exact union-probability method after the vectors are obtained.Instance difficulty still depends on explored partial paths, the number of vectors, capacity levels, and the tightness of demand, time, and budget requirements.Source: §6 · p. 28
• Future work includes parallel and vectorized search, adaptive selection of look-ahead conditions, and extensions to other multistate-network settings.The proposed directions include additional resource constraints, multiple sources or destinations, and alternative transmission requirements.Source: §6 · p. 28