carbs.utilities.graphs.k_shortest

k_shortest(log_cost_in, k)[source]

This implents k-shortest path algorithm.

This ports the implementation from here. to python. The following are comments from the original implementation.

Meral Shirazipour This function is based on Yen’s k-Shortest Path algorithm (1971) This function calls a slightly modified function dijkstra() by Xiaodong Wang 2004. * log_cost_in must have positive weights/costs Modified by BT VO Replaces dijkstra’s algorithm with Derek O’Connor’s Bellman-Ford-Moore implementation which allows negative entries in cost matrices provided there are no negative cycles and used in GLMB filter codes for prediction * netCostMatrix can have negative weights/costs

Parameters:

  • log_cost_in (Numpy array) – Input cost matrix, inf represents absence of a link

  • k (int) – Maximum number of paths to find

Returns:

  • paths (list): List with each element being a list of indices into the cost matrix for the shortest path

  • costs (list): List of costs associated with each path

Return type:

tuple containing