在R中利用igraph包计算NYC出租车网络两点间最短路径的技术问询

Hey there! Let's tackle this NYC Taxi shortest path issue you're hitting with igraph and shp2graph—I’ve run into similar hiccups working with spatial road networks, so let’s break down the most likely fixes:

1. First: Verify Your Spatial Graph is Built Correctly #

Before blaming get.shortest.paths(), make sure your converted igraph object accurately represents the NYC road network:

• After loading with readshpnw(), inspect the graph’s core components:

  library(shp2graph)
  library(igraph)
  
  # Load your shapefile
  nw <- readshpnw("nyc_roads.shp", ELComputed = TRUE)
  
  # Check vertex coordinates and edge attributes
  head(V(nw@graph)$x)  # Verify longitude values make sense for NYC
  head(V(nw@graph)$y)  # Verify latitude values
  head(E(nw@graph))    # Check edge start/end vertex IDs
  

• Ensure edge weights (like road length) exist and are valid:
  If shp2graph didn’t auto-populate a weight attribute, calculate it manually using vertex coordinates:

  # Calculate Euclidean distance as edge weight (adjust if you need Manhattan distance)
  E(nw@graph)$length <- sqrt(
    (V(nw@graph)$x[E(nw@graph)$from] - V(nw@graph)$x[E(nw@graph)$to])^2 +
    (V(nw@graph)$y[E(nw@graph)$from] - V(nw@graph)$y[E(nw@graph)$to])^2
  )
  
  # Confirm no NA weights (Dijkstra will fail with missing values)
  any(is.na(E(nw@graph)$length))  # Should return FALSE
  

• Visualize the graph to spot obvious errors (like disconnected components):

  plot(nw@graph, vertex.size = 1, edge.arrow.size = 0.1)
  

2. Fix get.shortest.paths() Usage #

Most issues stem from misconfiguring parameters here:

• Always explicitly define weights: The default behavior uses edge IDs as weights, which is not what you want for shortest path calculations.

  # Replace with your actual start/end vertex IDs
  start_vertex <- 123
  end_vertex <- 456
  
  # Correct call with weight parameter
  shortest_path <- get.shortest.paths(
    nw@graph,
    from = start_vertex,
    to = end_vertex,
    weights = E(nw@graph)$length,  # Use your valid weight attribute here
    mode = "all"  # Use "out" if dealing with one-way roads in NYC
  )
  

• Double-check vertex ID matching: If you’re using coordinates to find vertices (e.g., passenger pick-up/drop-off points), make sure you’re mapping them to the correct igraph vertex IDs:

  # Example: Find closest vertex to a pick-up coordinate
  pick_up_coord <- c(-74.006, 40.7128)  # NYC example coordinate
  start_vertex <- which.min(
    sqrt((V(nw@graph)$x - pick_up_coord[1])^2 + (V(nw@graph)$y - pick_up_coord[2])^2)
  )
  

3. Troubleshooting Persistent Issues #

If get.shortest.paths() still fails:

• Simplify the graph: shp2graph sometimes creates multiple edges between the same vertices, which can confuse path algorithms. Simplify it with:

  simplified_graph <- simplify(nw@graph, remove.multiple = TRUE, remove.loops = TRUE)
  

• Use alternative functions for validation:
  • distances() returns the shortest path length between vertices to confirm connectivity:

    distance <- distances(simplified_graph, from = start_vertex, to = end_vertex, weights = E(simplified_graph)$length)
    

  • If distance returns Inf, your start/end vertices are in disconnected components—you’ll need to fix your shapefile or add missing edges.

内容的提问来源于stack exchange，提问作者Anthony Niemiec