R, determine shortest path

I have a graph and need the shortest distance between all nodes. Now I made the following function,

shortestPath <- function(streets, length)
{
    streets <- matrix(streets, byrow=TRUE, ncol=2)    # from -> to
    g <- graph.data.frame(as.data.frame(streets))     # create graph, see plot(g)
    return <- shortest.paths(g, weights = length)     # return routes lengths
}

Here streets is a vector which contains data where we have an edge and length is (obviously) the length of the edge.

I have the following graph where each edge has length two, note that the graph has to be undirected.

You can use the following data to reproduce the problem.

# Data
edges <- c(1,2, 2,3, 3,4, 4,5, 2,6, 3,7, 4,8, 6,8);
length <- rep(2,8);
aantalNodes <- 8;

# Determine shortest path
routes <- matrix(shortestPath(edges,length), byrow=FALSE, ncol=aantalNodes);

We clearly see that the shortest path between node 6 and node 8 has length 2, however, this function returns length 4. What's going wrong? I'm already tinker with it for two days. Looking forward for you help!

---

You may want to have a look at the rownames and colnames of shortestPath(edges,length) . It's really rather revealing...

res <- shortestPath(edges,length)
res[order(as.integer(rownames(res))),
    order(as.integer(colnames(res)))]

链接地址: http://www.djcxy.com/p/35230.html

上一篇: 有一些限制的最短路径算法

下一篇: R，确定最短路径