Skip to content

Distances in shortestPath function (package spatgraphs)

4 messages · Julian Burgos, Tuomas Rajala

Original
Julian Burgos
# 
Dear list,

I have a question about the shortestPath function (in the package 
spatgraphs... a very useful package but with very sparse 
documentation).  The function finds the shortest connection between two 
nodes in a graph.  According to the documentation, the usage of the 
function is

shortestPath(i, j, g, pp=NULL, dbg=FALSE)

where i and j are the starting and ending nodes, g is the graph that 
defines de edges, and pp is a point pattern.  If pp is given, "the edges 
are of Euclidian length, otherwise each edge is of length 1.".

So this is my question:  if I give a point pattern, does the shortesPath 
function finds the shortest path in terms of distances between nodes or 
in terms of number of nodes?  In other words, will the algorithm select 
a shorter path in terms of distance even if it goes through a larger 
number of nodes?  I am asking because my graph  is very dense (has lots 
of points) in some areas, and it is very sparse in others.  I want to 
make sure that the algorithm actually picks the track with the shortest 
distance and not the track with the lowest number of nodes.
Thanks!

Julian
Tuomas Rajala
# 
Dear Julian,

the algorithm finds the shortest paths in a weighted graph with each
edge weight being the Euclidian distance between corresponding node
locations. Weights are constant 1 if 'pp', and hence the node
locations, are not provided. For reference, see e.g.
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

So, if
1. you give pp, the edges are weighted with Euclidian distances, and
the result is the geographical minimum distance needed to travel along
the graph from i to j,

2. you don't give pp, in which case each edge has weight 1, and the
result is the shortest path in term of edges needed to hop to get from
i to j.

To answer your question: Shortest path in terms of distance is given
by 1., and in term of nodes given by 2.

Sorry for the mix-up in terms: General graph term for the cost of
traveling each edge is 'weight'; I use 'length' in the docs, as it
makes sense in spatial context.

Hope this helps,
Tuomas R



2012/6/18 Julian Burgos <julian at hafro.is>
1 day later
Julian Burgos
# 
Great, thanks for the answer!
On m?n 18.j?n 2012 11:20, Julian Burgos wrote: