The Route with Fewer Stops Takes Longer

The maintenance cart can reach B directly from A in nine minutes. Going through C takes four minutes. A search that chooses the fewest relationships selects the direct route, even though the crew asked for the quickest one.

We need to define what “shortest” measures. Hop count treats every edge equally. Travel time assigns a cost to each edge, so the route choice must compare accumulated costs rather than the number of connections.

The fewest-hop shortcut loses to a longer route with lower accumulated minutes.

5

Minimum hops answers how many links must be followed. Minimum travel time answers how much edge cost accumulates. Neither is inherently the correct question; the operational objective decides.

A directed route can be traversable in one direction only. If a corridor is bidirectional, represent both permitted directions or use a graph projection whose orientation is deliberately defined.

Our route graph is directed, and every minutes property uses the same unit.

B is first discovered with cost nine through the direct edge. When C is expanded, the route through C offers a lower cost to B. The algorithm updates B’s best value rather than treating its first discovery as final.

A priority queue makes the lowest current candidate the next one to process. Older queued entries for a node can become stale after an improvement, so the code checks them against the best-known distance.

The visited-on-discovery rule from unweighted BFS does not implement this weighted objective.

direct=9
via_c=2+2
print({'direct':direct,'via_C':via_c})

{'direct': 9, 'via_C': 4}

A Python heap stores the candidate with the smallest first tuple value at its front. heappush adds a candidate; heappop removes the cheapest one. The second tuple item is the node ID, which also provides a deterministic tie break for these string IDs.

We do not need to find and delete an old heap entry when a better route appears. Update best and push the cheaper candidate. When the old entry eventually comes out, compare its cost with best and skip it if they differ. The program below isolates that mechanism before the challenge adds graph traversal.

The heap remembers candidates. The best dictionary records the current best estimate for each node.

import heapq
best={'B':9,'C':2}
pending=[(2,'C'),(9,'B')]
heapq.heapify(pending)
cost,node=heapq.heappop(pending)
proposed=cost+2  # C to B takes two minutes.
if proposed < best['B']:
    best['B']=proposed
    heapq.heappush(pending,(proposed,'B'))
while pending:
    cost,node=heapq.heappop(pending)
    if cost != best[node]:
        print('skip',node,cost)
        continue
    print('use',node,cost)

use B 4
skip B 9

Once the cheapest candidate is settled, nonnegative future edges cannot produce a cheaper route by leaving that settled frontier and later subtracting cost. That property supports Dijkstra’s decision rule.

Negative weights require another algorithm and careful treatment of negative cycles. A missing weight is not automatically zero. Validate the graph projection’s weight field and units before running the method.

The exercise accepts zero-cost edges but rejects negative or nonfinite costs.

A hop-oriented shortestPath pattern does not automatically minimise a minutes property just because the relationship contains it. Weighted algorithms such as GDS Dijkstra use an explicitly projected weight.

For the tiny setup below, the reference query enumerates bounded paths and orders their summed cost. It exposes the objective in ordinary Cypher, but it is not a scalable replacement for a dedicated weighted algorithm.

This reference is limited to a tiny acyclic graph with all relevant paths within three hops.

MATCH p=(a:Location {id:$start})-[:ROUTE*1..3]->(b:Location {id:$target})
WITH p, reduce(total=0, r IN relationships(p) | total+r.minutes) AS cost
RETURN [n IN nodes(p) | n.id] AS route, cost
ORDER BY cost, route
LIMIT 1

If the destination cannot be reached, return no distance, represented by None in the exercise. If start equals target, the empty route has cost zero. A reachable route can also legitimately have zero total cost.

Do not replace absence with zero. That would make a disconnected workshop look as though the cart were already there.

The challenge returns the minimum cost only, so equally cheap paths do not require a route-selection tie break.

A closed corridor or a restricted area must be removed before routing. Applying permission checks only after choosing the cheapest path can select an unusable route and obscure valid alternatives.

Travel times may change while the cart moves. A graph snapshot provides an estimate under stated conditions, not a guarantee about the physical journey. Validate operational safety separately from minimising cost.

The workshop filters ROUTE edges and computes costs from the supplied snapshot.