Shortest path in a street network

Question

I'm working with NYC taxi dataset. Street network are obtained using osmnx and red dots are taxi pickup GPS locations.

I did some map-matching. I projected the GPS locations to its nearest edge, and the projections are treated as nodes and added to the network (graph), its edges were updated accordingly. I get the following network. The yellow dots are the real nodes, and the purple dots are the projections of the GPS locations (also treated as nodes but differentiated by its attribute).

Next I want to find the shortest path between two purple dots. For instance I get the following.

The red line is obviously NOT the shortest path. It seems to me that the shortest_path function accounts for the direction of the edges (i.e. for an edge, it always goes from the starting point to the end point). Is there a way that I can get the true shortest path? In fact, I only want the shortest network distance between two points.

I guess I could duplicate each edge with its starting and end points reversed. But maybe there's a cleaner way to do this?

Answer 1

The current answer is incorrect because it allows travel the wrong way down a one-way street. In reality, you need to calculate two shortest paths: one from origin to destination and one from destination to origin. The shortest network distance in either direction is the minimum of these two.

(Note: if directionality doesn't matter because the mode, such as walking, does not follow street directionality constraints, then provide a network_type argument like walk when creating the graph to get a fully bidirectional graph.)

Complete minimal working example:

import networkx as nx
import osmnx as ox
ox.config(use_cache=True)

# get a graph, origin/destination nodes, and edge weight attribute
G = ox.graph_from_point((40.754830, -73.984049), network_type='drive')
orig = list(G)[10]
dest = list(G)[-10]
w = 'length'

# incorrect solution in other answer: route goes the wrong way down a one-way street
route1 = nx.shortest_path(nx.compose(G, G.reverse(copy=False)), orig, dest, weight='length')

# correct solution: finds the shortest trip in either direction while obeying one-ways
if nx.shortest_path_length(G, orig, dest, w) <= nx.shortest_path_length(G, dest, orig, w):
    route2 = nx.shortest_path(G, orig, dest, w)
else:
    route2 = nx.shortest_path(G, dest, orig, w)
    
print(route1 == route2) #False

# plot both routes to show how route1 goes the wrong way down a one-way
Gu = ox.get_undirected(G)
fig, ax = ox.plot_graph_routes(Gu, [route1, route2], ['c', 'y'])

Answer 2

I found a clean way for this. I can simply do

route = nx.shortest_path(nx.compose(G, G.reverse(copy=False)), source=9990000067, target=9990000003, weight='length')
fig, ax = ox.plot_graph_route(nx.compose(G, G.reverse(copy=False)), route)