Step-Free Routing with Weighted Graphs

Step-free routing is the concrete case that motivates the whole multi-profile design in Accessible & Multi-Profile Indoor Routing: given one attributed graph, compute a path that a wheelchair user, a parent with a pushchair, or a porter with a cart can actually traverse, by making every staircase impassable rather than merely expensive.

What “Step-Free Routing” Means #

Step-free routing is shortest-path search over a graph in which any edge that requires climbing or descending steps is treated as absent, not costly. The distinction is the entire subject. A step-free route may never include a stair edge; it may include a corridor, a doorway wide enough for a wheelchair, a ramp within an acceptable incline, or an elevator. Everything else about the search is ordinary Dijkstra — the only thing that makes it “step-free” is the weight function that returns an exclusion sentinel for stairs and a finite cost for step-free connectors.

The word “weighted” carries a second meaning here beyond exclusion. Among the step-free options, an elevator is not free: it has a call-and-wait cost that a flat corridor of the same length does not. A ramp near the maximum permitted incline is harder than a flat corridor. So the weight function does two jobs at once: it excludes impassable edges by returning None, and it penalises passable-but-costly edges by returning an inflated but finite number. The result is a route that is both legal (no steps) and humane (prefers the flat corridor to the long ramp when both work).

Minimal Working Example #

The example below builds a small networkx graph whose edges carry the accessibility attributes described in the parent section, defines a step-free weight callable, and runs Dijkstra. The stair edge between the lobby and the mezzanine is the trap: a distance-only router takes it because it is short, and a step-free router must refuse it and take the ramp instead.

import logging
from typing import Optional

import networkx as nx

logging.basicConfig(level=logging.INFO, format="%(asctime)s | %(levelname)s | %(message)s")
logger = logging.getLogger(__name__)

STAIR_SENTINEL = None          # returning None removes the edge from this profile's graph
ELEVATOR_WAIT_M = 8.0          # call-and-wait modelled as equivalent metres

G = nx.Graph()
#            u          v            space_class  step_free  incline  length_m
G.add_edge("lobby",    "mezz",      space_class="stair",    step_free=False, incline=0.0,  length_m=6.0)
G.add_edge("lobby",    "ramp_foot", space_class="corridor", step_free=True,  incline=0.0,  length_m=9.0)
G.add_edge("ramp_foot","mezz",      space_class="ramp",     step_free=True,  incline=4.5,  length_m=14.0)
G.add_edge("lobby",    "lift_a",    space_class="corridor", step_free=True,  incline=0.0,  length_m=5.0)
G.add_edge("lift_a",   "mezz",      space_class="elevator", step_free=True,  incline=0.0,  length_m=3.0)


def step_free_weight(u: str, v: str, attrs: dict) -> Optional[float]:
    """Return None for anything with steps; a finite, penalty-adjusted cost otherwise."""
    if not attrs["step_free"] or attrs["space_class"] == "stair":
        return STAIR_SENTINEL                       # hard exclusion, not a penalty
    base = float(attrs["length_m"])
    if attrs["space_class"] == "elevator":
        return base + ELEVATOR_WAIT_M               # passable but costs its wait
    if attrs["space_class"] == "ramp":
        return base * (1.0 + attrs["incline"] / 10.0)  # steeper ramp, higher cost
    return base


try:
    path = nx.dijkstra_path(G, "lobby", "mezz", weight=step_free_weight)
    logger.info("step-free path: %s", " -> ".join(path))
except nx.NetworkXNoPath:
    logger.warning("no step-free path to mezz; escalate, do not use stairs")
    path = []

Running it prints a route that goes lobby -> ramp_foot -> mezz (cost 9.0 + 14.0 × 1.45 ≈ 29.3) rather than the elevator branch (5.0 + 3.0 + 8.0 = 16.0)… and that comparison is the point: the elevator branch is actually cheaper, so Dijkstra returns lobby -> lift_a -> mezz. The direct lobby -> mezz stair (length 6.0) is never considered because step_free_weight returned None for it. Swap the elevator out of service — set its step_free to False — and the router correctly falls back to the ramp instead of ever touching the stair.

Step-Free Weight Reference #

Common Errors & Fixes #

A wheelchair route still contains a staircase. The weight function penalised the stair instead of excluding it — it returned something like attrs["length_m"] * 50 rather than None. A finite penalty is still finite, so on a link where every alternative is longer, the “avoided” stair wins. Return the sentinel:

# WRONG: a penalty is selectable when the detour is long enough.
# return attrs["length_m"] * 50
# RIGHT: None removes the edge from this profile's graph entirely.
if not attrs["step_free"] or attrs["space_class"] == "stair":
    return None

networkx.exception.NetworkXNoPath when a route visibly exists on the floor plan. Excluding the stairs disconnected the step-free subgraph — there is genuinely no ramp or elevator between the two components. This is a correct result, not a solver bug; do not “fix” it by relaxing the exclusion. Detect it and escalate to a human-readable message or the fallback routing architecture, and file the missing connector against the survey:

try:
    path = nx.dijkstra_path(G, src, dst, weight=step_free_weight)
except nx.NetworkXNoPath:
    logger.warning("step-free subgraph disconnected between %s and %s", src, dst)
    return None   # surface "no step-free route", never silently fall back to stairs

Elevators treated as free, so the router prefers a lift for a single-floor hop. Forgetting ELEVATOR_WAIT_M makes a 3 m elevator edge look cheaper than a 9 m flat corridor, and the router sends a step-free user to wait for a lift to travel one short segment. Add the call-and-wait cost so the elevator is chosen only when it genuinely shortens the journey, and tune the constant against observed dwell time rather than leaving it at zero.

Integration Point #

This reference is the smallest working piece of a larger design. The step-free weight callable here is one instance of the profile weight functions compiled in Accessible & Multi-Profile Indoor Routing — in production you would register it alongside default, assisted, and service profiles that all share this same graph. The graph it runs over is built from parsed geometry and carries stair, ramp, and elevator edges only because Level Mapping & Z-Axis Logic modelled the vertical connectors as distinct edge classes with real endpoints on each floor. When the step-free search returns no path, control passes to the deterministic tiers in Fallback Routing Architectures, which keep the session alive instead of dropping it.

Frequently Asked Questions #

Related #

• Accessible & Multi-Profile Indoor Routing — the broader design that registers this step-free profile alongside default, assisted, and service profiles over one topology.
• Level Mapping & Z-Axis Logic — how the stair, ramp, and elevator edges this search distinguishes are modelled across floors.
• Fallback Routing Architectures — where a disconnected step-free subgraph hands off so the session is never dropped.

This page is part of the Accessible & Multi-Profile Indoor Routing guide within the Indoor Mapping Architecture & Standards reference.