2000/09/01 
THIS and THAT 
Euler’s famous “Königsberg bridge” question, dating back as far as 1736, is often seen as the starting point of modern path finding – was it possible to find a path through the city of Königsberg crossing each of its seven bridges once and only once and then returning to the origin? Euler’s methods formed the basis of what is known as graph theory, and which in turn paved the way for path finding algorithms. Traditionally, network analysis, path finding and route planning have been the domain of graph theory and vector GIS, which is where most algorithms find their application. Contrary to such common wisdom, the research of this thesis for the Msc in GIS explores the topic of network analysis in raster GIS, using MFworks as example software. Current algorithms, procedures and network modelling techniques are investigated and common artefacts are explained.
Conclusions
An extension of Tomlin’s directional identifiers is proposed, allowing the modelling of non-planar features. Along with this, the integration of time- dependent travel cost variables is achieved through linking MFworks with an external Visual Basic application for updating the cost-of-passage surface, demonstrating that such interaction extends the inherent capabilities of a GIS engine. Another conclusion to be drawn from this paper is that network analysis in raster GIS is a variant of surface analysis.
Read online
MFWorks Tutorial
This insights gained in this thesis were later used for developing a tutorial for network analysis in raster GIS using MFWorks.
Reference
Husdal, J. (2000). How to make a straight line square. Network Analysis in Raster GIS with time-dependent cost variables. Unpublished. Thesis for the MSc in GIS at the University of Leicester, UK.
Related
- husdal.com: Network analysis in raster versus vector GIS
- husdal.com: Book Review: This is where raster GIS started
- husdal.com: How to use MFworks for network analysis
- husdal.com: Corridor analysis – a timeline of evolutionary development
More from husdal.com
MFworks has evolved from MAPFactory, originally designed by C. Dana Tomlin, the father of map ...
...well not really, but Geographic Information Systems and Cartographic Modeling by Tomlin spark ...
Network analysis in GIS is often related to finding solutions to transportation problems. In a ...
This tutorial was developed by Jan Husdal at the University of Utah, Salt Lake City, 2000-2002. ...
Locating a right-of-way for a linear facility such as a pipeline, a transmission line, a railway ...
2010/09/02: Book Review: Risk Modeling, Assessment, and Management
2010/08/30: Infrastructure Vulnerability
2010/08/28: Importance and Exposure – Measures of Road Network Vulnerability?
2010/08/27: Logipi – why you should listen to it
2010/08/26: The ISCRIM Newsletter 1/2010
2010/08/25: Blog Supply Chain Risk: Writer’s Block
2010/08/23: Supply Chain Risk: Culture Shock
2010/08/04: Book Review: Humanitarian Logistics
2010/07/11: WCTR 2010
The thesis is a very good overview over the different aspects of least-cost path calculations. But trying to understand the example of Fig. 3-9 I think I found a mistake: On the green path, the accumulated costs are 0 -> 2.1 -> 4.1 (!!!) -> 6.1, on the red one: 0 -> 1 -> 2.5 -> 5.3, and therefore the red path is optimal.
The argument that steepest descent is not optimal is not invalidated by this mistake. The full implementation of Dijkstra’s algorithm includes backlinks so that the optimal path is found – always!
Best wishes
Irmela
Thanks for your compliments on my now 10-year-old thesis. I am glad that it is still of some use. As to the figure, that is not my MY figure but taken from the reference mentioned. I did make the same calculations as that author and I did not see the ‘flaw’. Thanks for pointing that out.