R igraph：在 igraph 中查找最短路径，为其增加权重并搜索替代方案

Question

我玩 https://rdrr.io/rforge/osmar/src/demo/navigator.R（导航器演示）。我想找到几条路径而不是一条路径。

看来我无法使用 all_simple_paths 函数，因为它永远不会终止。在我找到

的最短路径后是否可能

route <- get.all.shortest.paths(gr_muc, from = as.character(hway_start_node), to = as.character(hway_end_node))[[1]]

增加整条路线的权重，用函数get.all.shortest.paths重新搜索，找到n个替代方案？这是正确的方法还是有替代方法？

提前致谢！

    library(tidyverse)
library(osmdata)
library(osmar) # (geosphere is inclued in osmar)
library(sf)
library(ggmap)
library(prettymapr)
library(leaflet)
library(igraph)
library(stplanr)
library(rgeos)

### Download and extract data: #######################################

download.file("http://osmar.r-forge.r-project.org/muenchen.osm.gz",
              "muenchen.osm.gz")

system("gzip -d muenchen.osm.gz")



### Import subset based on bounding box: #############################

src <- osmsource_osmosis(file = "muenchen.osm",
                         osmosis = "osmosis")

muc_bbox <- center_bbox(11.575278, 48.137222, 60000, 60000)

muc <- get_osm(muc_bbox, src)

hways_muc<-muc
gr_muc <- as_igraph(hways_muc)

 hway_start_node <- local({
  id <- find(muc, node(tags(v == "Sendlinger Tor")))[1]
  find_nearest_node(muc, id, way(tags(k == "highway")))
})

hway_start <- subset(muc, node(hway_start_node))

hway_end_node <- local({
  id <- find(muc, node(attrs(lon > 11.59 & lat > 48.150)))[1]
  find_nearest_node(muc, id, way(tags(k == "highway")))
})
hway_end <- subset(muc, node(hway_end_node))



route <- get.all.shortest.paths(gr_muc,
                                    from = as.character(hway_start_node),
                                    to = as.character(hway_end_node),
                                    mode = "all")[[1]]

Answer 1

增加路径的权重完全符合预期：

library(osmar)
library(igraph)

### Get data ----
src <- osmsource_api(url = "https://api.openstreetmap.org/api/0.6/")
muc_bbox <- center_bbox(11.575278, 48.137222, 1000, 1000)
muc <- get_osm(muc_bbox, src)

### Reduce to highways: ----
hways <- subset(muc, way_ids = find(muc, way(tags(k == "highway"))))
hways <- find(hways, way(tags(k == "name")))
hways <- find_down(muc, way(hways))
hways <- subset(muc, ids = hways)

#### Plot data ----
## Plot complete data and highways on top:
plot(muc)
plot_ways(muc, col = "lightgrey")
plot_ways(hways, col = "coral", add = TRUE)

### Define route start and end nodes: ----
id<-find(muc, node(tags(v %agrep% "Sendlinger Tor")))[1]
hway_start_node <-find_nearest_node(muc, id, way(tags(k == "highway"))) 
hway_start <- subset(muc, node(hway_start_node))

id <- find(muc, node(attrs(lon > 11.58 & lat > 48.15)))[1]
hway_end_node <- find_nearest_node(muc, id, way(tags(k == "highway")))
hway_end <- subset(muc, node(hway_end_node))

## Add the route start and and nodes to the plot:
plot_nodes(hway_start, add = TRUE, col = "red", pch = 19, cex = 2)
plot_nodes(hway_end, add = TRUE, col = "red", pch = 19, cex = 2)

### Create street graph ----
gr <- as.undirected(as_igraph(hways))

### Compute shortest route: ----
# Calculate route
route <- function(start_node,end_node) {
  get.shortest.paths(gr,
                    from = as.character(start_node),
                    to = as.character(end_node), 
                    mode = "all")[[1]][[1]]}
# Plot route
plot.route <- function(r,color) {
  r.nodes.names <- as.numeric(V(gr)[r]$name)
  r.ways <- subset(hways, ids = osmar::find_up(hways, node(r.nodes.names)))
  plot_ways(r.ways, add = TRUE, col = color, lwd = 2)
}

# Number of new ways to look for 
nways <- 10
# Weight factor applied to already found way
weightfactor <- 2

for (numway in 1:nways) {
  r <- route(hway_start_node,hway_end_node)
  color <- colorRampPalette(c("springgreen","royalblue"))(nways)[numway]
  plot.route(r,color)
  # Modify current route weight
  E(gr)[r]$weight <- E(gr)[r]$weight * weightfactor
}

R igraph：在 igraph 中查找最短路径，为其增加权重并搜索替代方案

R igraph: Finding shortest path in igraph, adding weight to it and search for alternative

r

shortest-path

igraph

osrm