pysal.explore.spaghetti.dijkstra

pysal.explore.spaghetti.dijkstra(ntw, cost, v0, n=inf)[source]

Compute the shortest path between a start node and all other nodes in an origin-destination matrix.

Parameters:
ntw : spaghetti.Network

spaghetti Network object.

cost : dict

key is tuple (start node, end node); value is float. Cost per edge to travel, e.g. distance.

v0 : int

Start node ID

n : float

integer break point to stop iteration and return n neighbors. Default is (‘inf’).

Returns:
distance : list

List of distances from node to all other nodes.

pred : list

List of preceeding nodes for traversal route.

Notes

Based on [Dij59].

Examples

>>> import pysal.explore.spaghetti as spgh
>>> from pysal.lib import examples
>>> ntw = spgh.Network(examples.get_path('streets.shp'))
>>> distance, pred = spgh.util.dijkstra(ntw, ntw.edge_lengths, 0)
>>> round(distance[196], 4)
5505.6682
>>> pred[196]
133