Shortest paths and OD matrices¶

This notebook covers the shortest-path helpers available for UrbanGraph. Distances are returned in the units of the selected edge weight: minutes for time_min and meters for length_meter.

# To install IduEdu in a clean environment:
# !pip install IduEdu

OSM_ID = 1114252

from iduedu import get_walk_graph

G_walk = get_walk_graph(osm_id=OSM_ID, simplify=True, keep_largest_subgraph=True)
G_walk.update_adjacency_matrix(weight="time_min")

sample_nodes = G_walk.nodes_gdf.index[:6].tolist()
source = sample_nodes[0]
destinations = sample_nodes[1:]
print(sample_nodes)

2026-07-07 15:18:59.464 | WARNING  | Removing 332 nodes outside the largest connected component. Retaining 19588 of 19920 nodes.

[0, 1, 2, 3, 4, 5]

Single-source distances¶

Use this for one origin and many possible destinations, for example a walking catchment around one point.

from iduedu import single_source_dijkstra_path_length

single = single_source_dijkstra_path_length(
    G_walk,
    source,
    weight="time_min",
    cutoff=15,
)

single.sort_values().head(10)

node
        0.0
       0.21
  0.323
  0.338
      0.438
      0.658
     1.563
     1.605
     1.648
     1.689
Name: dist, dtype: Sparse[float32, inf]

Multi-source distance to the closest source¶

All sources are inserted into one Dijkstra queue. The result gives the distance to the nearest source, not one row per source.

from iduedu import multi_source_dijkstra_path_length

multi = multi_source_dijkstra_path_length(
    G_walk,
    source_nodes=sample_nodes[:3],
    weight="time_min",
    cutoff=15,
)

multi.sort_values().head(10)

node
        0.0
        0.0
        0.0
      0.228
  0.323
  0.338
  0.367
      0.448
      0.793
      0.844
Name: dist, dtype: Sparse[float32, inf]

Nearest source label and distance¶

Use this when the winning source node is needed along with the shortest distance.

from iduedu import multi_source_dijkstra_nearest_source

nearest = multi_source_dijkstra_nearest_source(
    G_walk,
    source_nodes=sample_nodes[:3],
    weight="time_min",
    cutoff=15,
)

nearest.head(10)

	source_node	dist
node
0	0	0.0
1	1	0.0
2	2	0.0
3	2	0.228
4	2	0.448
5	1	0.844
6	1	0.793
7	1	1.019
8	1	0.972
9	1	1.583

Independent parallel searches¶

dijkstra_path_length_parallel keeps one sparse row per source. This is useful when each origin needs its own accessibility profile.

from iduedu import dijkstra_path_length_parallel

parallel = dijkstra_path_length_parallel(
    G_walk,
    source_nodes=sample_nodes[:3],
    weight="time_min",
    cutoff=15,
    max_workers=4,
)

parallel.iloc[:, :8]

node	0	1	2	3	4	5	6	7
0	0.0	3.18	0.21	0.438	0.658	2.477	2.387	2.302
1	3.18	0.0	2.97	2.742	2.522	0.844	0.793	1.019
2	0.21	2.97	0.0	0.228	0.448	2.267	2.177	2.092

Origin-destination matrix¶

od_matrix accepts graph node ids or GeoDataFrames. With node ids, rows follow origins_nodes and columns follow destination_nodes.

from iduedu import od_matrix

od = od_matrix(
    G_walk,
    origins_nodes=sample_nodes[:3],
    destination_nodes=destinations,
    weight="time_min",
    threshold=30,
    max_workers=4,
)

od

	1	2	3	4	5
0	3.18	0.21	0.438	0.658	2.477
1	0.0	2.97	2.742	2.522	0.844
2	2.97	0.0	0.228	0.448	2.267

Method equivalents¶

The same helpers are also available as UrbanGraph methods.

G_walk.single_source_dijkstra_path_length(source, cutoff=15).head()
G_walk.multi_source_dijkstra_path_length(source_nodes=sample_nodes[:3], cutoff=15).head()
G_walk.multi_source_dijkstra_nearest_source(source_nodes=sample_nodes[:3], cutoff=15).head()
G_walk.dijkstra_path_length_parallel(source_nodes=sample_nodes[:3], cutoff=15, max_workers=4).iloc[:, :5]
G_walk.od_matrix(origins_nodes=sample_nodes[:3], destination_nodes=destinations, threshold=30)

	1	2	3	4	5
0	3.18	0.21	0.438	0.658	2.477
1	0.0	2.97	2.742	2.522	0.844
2	2.97	0.0	0.228	0.448	2.267