igraph-help
[Top][All Lists]

## [igraph] shortest paths in a undirected weighted graph

 From: federico vaglio Subject: [igraph] shortest paths in a undirected weighted graph Date: Wed, 6 Oct 2010 23:42:03 +0200

Hi to all,
is there a way to get all shortest paths, not just lengths, between two vertices in a undirected weighted graph?

get.shortest.paths function has "weights" argument but gives only one shortest path, even if more than one shortest path exist between given vertices.

get.all.shortest.paths function returns all possible shortest paths but ignores edge weights, even if passed graph has a weight attribute.

Example code.

require(igraph)

# create a graph with 5 vertices
g <- graph.empty(5, dir=FALSE)

g <- add.edges(g, c(0, 1, 0, 2, 0, 3, 1, 4, 2, 4, 3, 4))

# edge weigths
E(g)\$weight <- c(1, 1, 2, 1, 1, 1)

# use weights but return only one path
get.shortest.paths(g, from=0, to=4)

#
# my result
#[[1]]
#[1] 0 2 4

# return all shortes paths but ignore weights
get.all.shortest.paths(g, from=0, to=4)

#
# my result
#[[1]]
#[1] 0 3 4
#
#[[2]]
#[1] 0 2 4
#
#[[3]]
#[1] 0 1 4