A Python Algorithm for Shortest-Path River Network Distance Calculations Considering River Flow Direction

Nicolas Cadieux, Margaret Kalacska, Oliver T. Coomes, Mari Tanaka and Yoshito Takasaki
Additional contact information
Nicolas Cadieux: Department of Geography, McGill University, Montreal, QC H3A 0B9, Canada
Margaret Kalacska: Department of Geography, McGill University, Montreal, QC H3A 0B9, Canada
Oliver T. Coomes: Department of Geography, McGill University, Montreal, QC H3A 0B9, Canada

Data, 2020, vol. 5, issue 1, 1-14

Abstract: Vector based shortest path analysis in geographic information system (GIS) is well established for road networks. Even though these network algorithms can be applied to river layers, they do not generally consider the direction of flow. This paper presents a Python 3.7 program (upstream_downstream_shortests_path_dijkstra.py) that was specifically developed for river networks. It implements multiple single-source (one to one) weighted Dijkstra shortest path calculations, on a list of provided source and target nodes, and returns the route geometry, the total distance between each source and target node, and the total upstream and downstream distances for each shortest path. The end result is similar to what would be obtained by an “all-pairs” weighted Dijkstra shortest path algorithm. Contrary to an “all-pairs” Dijkstra, the algorithm only operates on the source and target nodes that were specified by the user and not on all of the nodes contained within the graph. For efficiency, only the upper distance matrix is returned (e.g., distance from node A to node B), while the lower distance matrix (e.g., distance from nodes B to A) is not. The program is intended to be used in a multiprocessor environment and relies on Python’s multiprocessing package.

Keywords: weighted Dijkstra; GIS; NetworkX; Amazonia (search for similar items in EconPapers)
JEL-codes: C8 C80 C81 C82 C83 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2306-5729/5/1/8/pdf (application/pdf)
https://www.mdpi.com/2306-5729/5/1/8/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jdataj:v:5:y:2020:i:1:p:8-:d:309637

Access Statistics for this article

Data is currently edited by Ms. Cecilia Yang

More articles in Data from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().