A journey is more than connected places

Each flight is an edge with a departure time, arrival time, capacity, and rules about which connection can follow it. A connection is useful only if the passenger can make it. I approached multi-hop carpool routing with the same mental model.

A ride is a scheduled segment with pickup and drop-off points, time windows, available seats, and a maximum acceptable detour. A rider's journey can be assembled from several segments, provided each handoff is feasible.

A route diagram connecting an origin to a destination through two scheduled rides and a transfer buffer.
A route is valid only when each transfer works in both space and time.

Representing time in the graph

Locations can become graph nodes and ride segments directed edges. But a city-only graph loses the most important information: time. If one ride reaches a transfer point at 10:20 and the next departs at 10:10, the geographic route connects while the itinerary does not.

A time-dependent graph keeps locations as nodes but evaluates each ride against the rider's arrival time. A time-expanded graph makes each relevant location-and-time pair a distinct state, such as “Pune at 10:20,” so schedules and waiting become explicit. The expanded graph is larger, but transfer logic can be easier to inspect.

Search, score, and preserve choices

Dijkstra's algorithm finds a least-cost route when edge costs are non-negative. A* can reduce exploration when a valid lower-bound heuristic is available; straight-line distance can help estimate remaining travel time, but it must not overstate the true minimum if the heuristic is to remain admissible.

For scheduled rides, edge cost depends on time. The search must respect departure availability, transfer buffers, and connection feasibility instead of pretending every ride is always available.

“Best route” also needs a definition. The quickest trip may involve three transfers; the simplest may arrive later but use one handoff. A generalized cost can consider arrival time, total duration, waiting, transfer count, detour, and reliability. Keeping a small Pareto frontier—routes not dominated across these criteria—can preserve meaningful alternatives without overwhelming the rider.

A connected path must still be a usable trip

The flight analogy has limits. A missed flight is inconvenient; a missed carpool handoff may strand someone. Transfer buffers, clear pickup instructions, live updates, and revalidation are essential. Search results are suggestions, not reservations: seat availability must be checked again when a rider books, and any seat hold needs an explicit expiry.

I am building this as a mobility problem with a trust layer, not just a shortest-path demo. The algorithm can propose a clever route; the product still has to make that route understandable, feasible, and safe to accept. That is the real engineering challenge: turning a mathematically connected path into a journey a person can rely on.

Make the search practical at platform scale

A production search should narrow candidates before running an expensive route search. Spatial indexing can find rides near the origin, destination, and plausible transfer points. Time-window filters remove departures that cannot fit the rider's schedule. Only then does the graph search evaluate feasible continuations.

Search limits are product rules, not arbitrary algorithm shortcuts. A maximum number of transfers, a bound on total detour, and a reasonable horizon keep results understandable and prevent a combinatorial explosion. The interface should say when a route was excluded because of a constraint rather than imply that no route exists in the whole network.

The system also needs to cope with change. A ride may be cancelled, a seat may be taken, or a driver may alter a stop. Keep route suggestions versioned against their underlying ride data, revalidate before booking, and make a changed itinerary go through a fresh confirmation rather than silently swapping a transfer.

Trust and privacy belong in the route model

A mathematically short path is not necessarily an acceptable trip. Transfer points need to be practical meeting places, wait times should avoid unsafe or unreasonable gaps, and each segment must satisfy the rider's accessibility and preference constraints. These constraints need to be explicit inputs, not hidden penalties that make the route difficult to explain.

Trust signals require equally careful handling. Verified reviews can contribute evidence about reliability, but sentiment analysis is noisy and can encode sarcasm, language differences, or coordinated abuse. It should be combined with verification and policy rules, and severe restrictions need human review, an auditable reason, and a way to appeal.

Privacy-first vehicle details reduce unnecessary exposure before a match is meaningful. The platform should reveal only what a verified rider needs at the right stage, while retaining the minimum operational information required to handle safety reports. Privacy is a staged disclosure design, not a promise that the system stores no sensitive information.

Make transfer feasibility a first-class contract

A transfer edge is not simply “the next ride starts nearby.” It is a contract between two ride segments: the first must reach a compatible meeting point, the second must leave late enough for the rider to get there, and the combined itinerary must remain inside the requested arrival window. The minimum transfer buffer can vary by location, accessibility needs, and whether a walk between pickup points is required.

I model a candidate itinerary as immutable legs plus derived connection data. That makes it possible to recalculate feasibility when a ride changes without mutating the user's original search request. It also gives the interface concrete reasons for rejecting an otherwise nearby option: the departure is too early, the walk is too long, the wait exceeds the limit, or the vehicle has no remaining seat.

A Spring Boot service can keep the responsibilities separate: an adapter fetches candidate rides, a routing component explores feasible continuations, and an itinerary composer converts the winning path into a stable response. This is a design sketch rather than a claim about a deployed production service; the important boundary is that graph search returns candidates while booking revalidates inventory and creates a seat hold transactionally.

Illustrative connection check · java
boolean canConnect(Ride first, Ride next, Duration minBuffer, Duration maxWait) {
    if (!first.dropoff().equals(next.pickup())) return false;
    Duration wait = Duration.between(first.arrivesAt(), next.departsAt());
    return wait.compareTo(minBuffer) >= 0
        && wait.compareTo(maxWait) <= 0
        && first.arrivesAt().isBefore(next.departsAt());
}

Choose an algorithm by the promise you can keep

Dijkstra is a strong baseline when every transition has a non-negative cost and the state includes everything needed to determine the next feasible ride. A* can reduce work when its heuristic is a genuine lower bound—for example, straight-line distance divided by an optimistic maximum speed. A heuristic that overestimates can make the search faster but invalidates the shortest-path guarantee.

The bigger decision is often not Dijkstra versus A*. It is which constraints belong in the state, which are hard exclusions, and which are soft preferences. A maximum transfer count is a hard bound; a preference for shorter waits may be a cost. Mixing these categories can produce surprising results and makes the score hard to explain.

For an early product, a bounded, deterministic search with explicit limits is often more useful than a theoretically sophisticated planner that returns opaque choices. Record why a candidate was discarded, make scoring weights inspectable, and compare ranked results against hand-built scenarios before tuning for speed.

ChoiceBest fitTrade-off
DijkstraReliable baseline for non-negative route costsMay explore more of the candidate graph
A*Large searches with a valid lower-bound heuristicCorrectness depends on an admissible heuristic
Time-expanded graphExplicit schedules and transfer statesMore vertices and edges as time resolution grows

Treat search results as expiring proposals

A route result is a snapshot, not a promise that all seats still exist. Each response should carry enough version and expiry information for the booking flow to revalidate every leg. If one segment disappears, the system should explain which connection broke and offer a fresh search; silently replacing a driver or transfer undermines informed consent.

Idempotency keys make a retry safe when a rider submits a booking and the response is lost. A short-lived hold can reserve all required seats together or release them as a unit, avoiding a partially booked itinerary. These mechanics are as important to a practical multi-hop journey as the path-finding algorithm itself.

The product succeeds when it can explain the route, show the waits and handoffs, protect private details until the rider is verified, and recover cleanly when availability changes. A shortest path is only the beginning of that promise.

Rank routes with an explainable objective

A ranking function turns product priorities into behavior, so its units and limits deserve review. One practical score can combine elapsed minutes, transfer count, expected wait, detour, and a reliability penalty. Normalize each term before weighting it; otherwise, a large value measured in minutes can dominate a small count simply because the numbers have different scales. Keep hard safety constraints outside this score so a cheap but infeasible trip can never win.

The score should also preserve diversity. If the top ten results are nearly identical itineraries with the same first leg, the search has not helped the rider compare meaningful choices. Group by shared legs or transfer pattern, cap near-duplicates, and present a few alternatives such as fastest, fewest transfers, and lowest wait. Explain those labels with visible details instead of exposing a mysterious numerical rating.

Weights are hypotheses about user preferences, not permanent truths. Test them against realistic journeys: a direct ride with a modest detour, two short rides with a reliable transfer, a long layover that improves arrival certainty, and a route that is fast but depends on a narrow connection. Ask reviewers which option they would choose and why. If the ordering conflicts with the explanation shown in the UI, either the score or the product language needs revision.

The same evaluation set can catch regressions as route supply changes. Keep deterministic fixtures for transfer boundaries, late departures, cancellations, duplicated rides, and maximum detours. Add property checks such as non-decreasing arrival times across legs and no repeated ride in a path. Then benchmark candidate generation separately from graph traversal; optimizing the search loop will not help if spatial filtering dominates the request.