shortest_path

shortest_path(frm, to, weight, destinations, edge_index=None, node_count=None)

Solve the shortest paths through a network.

Mirrors the C# Dijkstra.Solve overloads: solves the cheapest route from EVERY node of a directed, weighted graph to a set of destination nodes at once, running the search backwards from the destinations. The answer is a routing table – for each node, which neighbour to step to, along which edge, and at what remaining cost.

Node indices are 0-based in both corehydropy and corehydror, matching the C# result table the two packages share; a graph with n nodes uses indices 0 to n - 1. Unreachable nodes carry cost = inf with next_node = -1 and edge_index = -1, and a destination node carries cost = 0 with next_node equal to its own index.

Costs accumulate in single precision, because the ported solver does (C# declares float Weight and its own tests assert the table by exact float equality). Fractional weights therefore round to float before they are summed.

Parameters

Name	Type	Description	Default
frm	array_like	Arrays of the same length, one element per directed edge: the start node index, the end node index, and the cost of traversing the edge. frm and to must be whole, non-negative numbers. (frm, not from, because from is a Python keyword; the R twin spells it from.)	required
to	array_like	Arrays of the same length, one element per directed edge: the start node index, the end node index, and the cost of traversing the edge. frm and to must be whole, non-negative numbers. (frm, not from, because from is a Python keyword; the R twin spells it from.)	required
weight	array_like	Arrays of the same length, one element per directed edge: the start node index, the end node index, and the cost of traversing the edge. frm and to must be whole, non-negative numbers. (frm, not from, because from is a Python keyword; the R twin spells it from.)	required
destinations	array_like or int	One or more destination node indices. With several destinations, each node keeps whichever destination it reaches most cheaply.	required
edge_index	array_like	An array the same length as frm, labelling each edge (typically an index into whatever the edges came from – a river reach, a road segment). Defaults to range(len(frm)). These labels are what the edge_index result column reports, and they need not be distinct.	None
node_count	int	Defaults to max(frm, to) + 1; supply a larger value to include isolated nodes carrying no edge, which then report cost = inf. A value below max(frm, to) + 1 is an error: the graph would not fit the routing table it asks for.	None

Returns

Name	Type	Description
	numpy.ndarray	One row per node, in node-index order, with columns [next_node, edge_index, cost].

Examples

>>> from corehydropy import shortest_path
>>> shortest_path([0, 1], [1, 2], [1, 1], destinations=2, node_count=4)
array([[ 1.,  0.,  2.],
       [ 2.,  1.,  1.],
       [ 2., -1.,  0.],
       [-1., -1., inf]])