Premium
Shortest Distances in a Modified Transportation Network
Author(s) -
Oudheusden Dirk L.
Publication year - 1977
Publication title -
geographical analysis
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.773
H-Index - 65
eISSN - 1538-4632
pISSN - 0016-7363
DOI - 10.1111/j.1538-4632.1977.tb00578.x
Subject(s) - shortest path problem , computer science , floyd–warshall algorithm , set (abstract data type) , computation , k shortest path routing , simple (philosophy) , algorithm , path (computing) , point (geometry) , mathematical optimization , average path length , shortest path faster algorithm , matrix (chemical analysis) , constrained shortest path first , theoretical computer science , graph , mathematics , computer network , philosophy , geometry , epistemology , programming language , materials science , composite material
Taking as the starting point an undirected source network and a set of possible new links that can be used to extend the source network, a method is proposed to determine, by simple inspection of a matrix tableau, all shortest distances in any extended network, without using a shortest path algorithm. In consequence, this method may be a useful tool for analyzing and judging network extensions. In particular, computation time can be saved in many complex network optimization methods that use shortest path algorithms. The computer experiments show that the method is feasible even when an extended network may differ from the source network by several dozens of branches.