trplearn.shortest_path module

class trplearn.shortest_path.TropicalShortestPath

Bases: object

All-pairs shortest path solver using tropical (min-plus) algebra. This class acts as an interpretation layer over the algebraic star() operation.

distance_matrix_

The calculated all-pairs shortest path distance matrix.

Type:

MinPlus

Examples

>>> import numpy as np
>>> from trplearn.shortest_path import TropicalShortestPath
>>> adj = [[0, 3, np.inf], [np.inf, 0, 1], [np.inf, np.inf, 0]]
>>> tsp = TropicalShortestPath()
>>> tsp.compute(adj)
>>> tsp.distances
array([[0., 3., 4.],
       [inf, 0., 1.],
       [inf, inf, 0.]])

compute(adjacency_matrix)

Compute the shortest path distance matrix.

Parameters:

adjacency_matrix (array-like) – Weighted adjacency matrix of the graph.

Returns:

self

Return type:

object

property distances

Return the calculated distance matrix as a numpy array.

get_distance(start_node, end_node)

Get the shortest distance between two specific nodes.

Parameters:

• start_node (int) – Index of the starting node.

• end_node (int) – Index of the destination node.

Returns:

distance

Return type:

float

trplearn.shortest_path.all_pairs_shortest_paths(adjacency_matrix)

Compute all-pairs shortest paths using Min-Plus algebra.

Parameters:

adjacency_matrix (array-like) – Weighted adjacency matrix of the graph. Use np.inf for no edge between nodes.

Returns:

The all-pairs shortest path distance matrix.

Return type:

MinPlus