Find the minimum total weighted path between two nodes on a weighted graph — in single-source single-destination, single-source all-destinations, or all-pairs variants. Foundational graph-OR problem; classical algorithms are Dijkstra, Bellman-Ford, Floyd-Warshall. The most frequently invoked OR algorithm in modern industry.
In plain words
Sound familiar?
- We are a domestic parcel-routing operator — for 5,000-50,000 parcels per day we need shortest-time routes from the central depot to customer addresses; we need a multi-criteria optimisation across travel time, distance and fuel.
- We run an urban field-service operation with 10-50 vehicles (plumbing, electrical, white-goods repair, HVAC); we compute customer-to-customer travel times and we want a traffic-aware computation engine.
- We are a municipal traffic management centre; we want a bridge between real-time congestion data and the static map network to provide traffic-aware shortest path for emergency services (ambulance, fire, police).
- We are a telecom backbone-network planner; we compute the lowest-latency packet-forwarding path between two switches (or two POPs); routing protocols like OSPF (Open Shortest Path First) run this computation underneath.
- We are a supply-chain planner; on a factory-port-warehouse-customer network we need the cheapest flow cost between every pair of nodes (all-pairs shortest path) — across multi-modal transport choices.
- We are a tollway operator or a haulage company; for long-haul routing we run a three-criterion (fuel + toll + driving hours) shortest path; the static graph is insufficient, we are looking for time-dependent shortest path.
- Our software team started with a direct Dijkstra implementation, but real-time queries on large graphs (1M+ nodes, country-scale road network) are too slow — we are evaluating preprocessing-based (contraction hierarchies) solutions.
Why it matters
How it's solved
Technical depth
How it's solved
Technical depthIn one sentence: Given nodes (intersections) + weighted edges (distance/time), use Dijkstra when edges are non-negative (at each step pick the closest neighbour and update neighbour distances), Bellman-Ford when negative edges are possible, Floyd-Warshall when an all-pairs distance matrix is needed — each guarantees the optimum.
This problem is studied in the Operations Research (the discipline that uses math and computers to solve business decisions) literature as the Shortest Path Problem (SPP) — the foundational graph-OR problem, 60+ years mature. Three core variants: single-source single-destination (one point-to-point), single-source all-destinations (from one source to all targets), all-pairs (every pair). Classical foundational algorithms date to the late 1950s and 1960s: Dijkstra for non-negative-edge graphs, Bellman-Ford for negative-edge graphs, Floyd-Warshall for all-pairs; modern preprocessing-based contraction hierarchies achieve sub-millisecond query time on country-scale road networks. Three stages:
1. Modelling. Input data: (a) graph structure — node set V (intersections, locations, switches), edge set E (roads, connections), edge weights w(u,v) (distance, time, cost, latency), directed (one-way street) or undirected (two-way), edge weights non-negative or possibly negative, with or without negative cycles, (b) query type — single point-to-point (source s, target t), single-source all-destinations (source s, target V), all-pairs (every i,j pair), (c) dynamism — graph weights static, time-dependent (traffic that varies by time of day), or with real-time updates (accident closures, weather), (d) multi-criteria — single-objective (only time) or multi-objective (time + distance + fuel + toll); multi-objective with Pareto-optimal paths or weighted sum, (e) constraints — road-type bans (truck cannot enter certain roads, ambulance exempt from some constraints), time windows (working hours), capacity (load to carry). Decision variables: edge sequence on the graph (s → … → t), per-edge “on-the-path or not” variable. Objective: minimum sum of edge weights.
2. Solver-driven decision. Algorithm choice depends on graph and query type:
(a) Dijkstra — non-negative edges, single-source. Greedy (pick the locally best choice at each step): at each step, extract the unvisited node with the smallest tentative distance from a priority queue and update its neighbours’ distances. Binary heap implementation O((V+E)logV), Fibonacci heap O(E + V logV). In practice: single-source single-destination / single-source all-destinations, small-mid-scale static graphs (1K-100K nodes).
(b) Bellman-Ford — supports negative edges. Relaxation (re-checking each edge for “is there a shorter path now”) across all edges V-1 times. Complexity O(VE). Negative-cycle detection: if an update still occurs at iteration V, a negative cycle exists and shortest path is undefined. Use cases: graphs with negative edges (financial arbitrage, network flow back-flow), distance-vector routing protocols.
(c) Floyd-Warshall — all-pairs, small graph. Dynamic programming: O(V³) time, O(V²) memory. In practice: V ≤ 1,000 nodes, when all-pairs is needed. Supports negative edges (without cycles).
(d) A — heuristic-guided single point-to-point.* Goal-directed variant of Dijkstra; a heuristic h(v) (e.g. Euclidean / great-circle distance) guides node priorities. Hart, Nilsson and Raphael (1968). In practice: single-source single-destination on geographic road networks, game-map pathfinding. Faster on average than Dijkstra; if the heuristic is admissible (h ≤ true distance), optimum is guaranteed.
(e) Bi-directional search. Run Dijkstra/A* forward from the source and backward from the target; stop when the two searches meet. Typically 2-4x faster than one-direction Dijkstra.
(f) Contraction Hierarchies (Geisberger et al. 2008) — modern preprocessing-based for country-scale road networks. The graph is preprocessed once (nodes are ‘contracted’ in a hierarchical order, shortcuts added); each subsequent query is answered in sub-millisecond time. Field-standard approach for real-time navigation on country-scale (10M+ edges) road networks. ALT (A*, Landmarks, Triangle inequality), Transit Node Routing and Hub Labels are other modern preprocessing-based methods.
(g) Time-dependent shortest path — traffic-aware. Edge weights are functions of time w(u,v,t); travel time depends on the departure time t. Static Dijkstra generalises; if the FIFO property holds (later-departure-no-earlier-arrival) the problem is polynomial-time. In practice: a routing engine fed by traffic-prediction data.
(h) Stochastic shortest path. Edge weights are random variables (e.g. traffic distribution); expected-value or risk-adjusted (CVaR) shortest path; Polychronopoulos-Tsitsiklis (1996).
3. Field integration. Output is three-layered: (a) operational — address-to-address route display in the driver mobile app / parcel-delivery route / field-service technician app, integrated with navigation, (b) planning — the shortest path matrix is invoked as a subroutine under VRP/TSP optimisation in daily route planning software, (c) strategic / analytical — supply-chain network analysis, telecom network bottleneck reports, all-pairs distance / time matrix for decision support. Upstream integration: ERP (order addresses), TMS (transport management system), map service (geocoding + road-network data), traffic data service (real-time prediction), fleet-tracking GPS data. Quarterly operations committee: shortest path query volume, average query time, traffic prediction drift (actual vs plan), route-change rate (recomputation triggers).
Alternatives
Manual + map service + driver experience
FreeMap service free tier, zero development cost
Who it fits: Small operation (1-10 vehicles/day), 10-50 stops/vehicle, known static routes
- + Zero software investment
- + Driver field knowledge counts
- + Phone-based real-time traffic response
- − No optimum guarantee, intuitive driver route inflates distance by 15-30%
- − No multi-criteria (time + fuel + toll) computation
- − No data capture — performance not measured
- − Beyond 10 vehicles, planner capacity is exceeded
Map service API + in-house integration
cloudPer-query pricing; $0.003-0.01/query, at 50K parcels/day this is $2K-8K/month
Who it fits: Mid operation (50-500 vehicles, 50K-500K stops/day), traffic-aware queries needed
- + Mature traffic data integrated
- + Address geocoding integrated
- + API easy to consume, short development time
- − Per-query cost becomes expensive at high volume
- − Algorithm is a black box, control limited
- − Vendor lock-in (map service contract)
- − Does not scale for all-pairs / large matrix queries
Open-source road-network engine + own servers
Open SourceLicence free; in-house build + servers 6-12 weeks or $100K-300K consulting + $15K-50K/year infrastructure
Who it fits: Operation with a tech team, high-volume queries (1M+/day), specialised constraints (truck road-type bans)
- + No licence cost, no per-query fee
- + Algorithm choice in your control (Dijkstra, A*, contraction hierarchies)
- + Specialised constraints (truck access, ambulance exemption) can be embedded
- + Data ownership stays in-house
- + 30+ TR theses (YÖK) reference implementations available
- − Road-network data (OpenStreetMap quality) requires periodic updates
- − Traffic data requires a separate provider
- − In-house OR specialist + infrastructure team required
- − Academic prototype to production: 3-6 months
International routing / TMS platform
Enterprise€300K-2M licence + €100K-500K/year maintenance
Who it fits: Large operation (500+ vehicles, multi-site, 1M+ stops/day), full TMS integration
- + Mature shortest path + VRP module integrated
- + Multi-criteria (time + cost + fuel + toll) standard
- + Time-dependent + stochastic variants supported
- + Traffic service comes in the bundle
- − High licence + long (12-24 month) rollout
- − Local road-network calibration extends the project
- − Algorithm is a black box — preprocessing parameter control limited
- − High single-supplier lock-in risk
Recommendation
Ask in the meeting
- Which approach does the shortest path algorithm use — Dijkstra (binary heap, Fibonacci heap), A*, bi-directional search, contraction hierarchies, ALT? What is the average query time on a country-scale road network (10M+ edges)?
- Are negative edges supported (Bellman-Ford)? Is negative-cycle detection available? In which scenarios (financial arbitrage, back-flow) is Bellman-Ford triggered?
- Is time-dependent (traffic-aware) shortest path supported? Which source provides the traffic data, and at what frequency (5-min, 15-min, hourly)? Is the FIFO property guaranteed?
- Where does road-network data come from (OpenStreetMap, commercial map service, national road inventory)? What is the data update cycle? How are road types (motorway, divided highway, urban, heavy-vehicle access) modelled as constraints?
- Is all-pairs shortest path (Floyd-Warshall, Johnson) supported, up to what scale (how many nodes)? How is the all-pairs distance matrix produced for a supply-chain network analysis?
- Is multi-criteria (time + distance + fuel + toll) optimisation supported — weighted sum or Pareto-optimal paths? Can the user tune the multi-objective parameters?
- In a pilot with real operational data (8-12 weeks), what savings report can be produced against the previous manual / existing-system route — fuel, delivery time, driver hours, route-change rate?
- If the contract ends, in which standard format (GeoJSON, GraphML, CSV) can we export the road-network data, traffic calibration data, query history and route archive?
Technical details
Editor’s note
In plain speech this problem is called “shortest route”, “route computation” or “navigation”. In the academic literature the canonical name is Shortest Path Problem (SPP), the foundational graph-OR problem. Edsger Dijkstra (1959), in a two-page Numerische Mathematik paper, defined a polynomial-time algorithm for non-negative-edge graphs — this paper is among the most-cited in computer science. Richard Bellman (1958), in a Quarterly of Applied Mathematics paper, introduced the negative-edge-capable Bellman-Ford. Robert Floyd (1962), in Communications of the ACM algorithm 97 (a one-paragraph paper), developed all-pairs Floyd-Warshall. Ahuja, Magnanti and Orlin (1993) Network Flows is the canonical textbook of the field. Modern preprocessing-based approaches (Geisberger et al. 2008 — contraction hierarchies) deliver sub-millisecond query time on country-scale road networks.
Distinction from #068 (TSP): TSP is the visit-all-nodes tour problem — visit each of N nodes exactly once and return to the start, NP-hard, the foundational combinatorial-optimisation problem. Shortest path is the single point-to-point or single-source all-destinations problem — polynomial-time (Dijkstra O((V+E)logV), Bellman-Ford O(VE), Floyd-Warshall O(V³)). The complexity gap is large: for a 1,000-node graph Dijkstra finishes in milliseconds, TSP runs for hours-days. TSP calls shortest path as a subroutine: the pairwise distance matrix is computed by shortest path, then TSP solves the tour problem on top.
Distinction from #069 (CVRP): CVRP is capacitated fleet routing — multiple vehicles, capacity-constrained, customers served collectively. CVRP calls shortest path as a subroutine: customer-to-customer and depot-to-customer distances are computed by shortest path, then CVRP solves the vehicle-customer assignment + route-order problem. In this stack, shortest path plays the “fill the graph weight matrix” role and CVRP plays the “vehicle-customer assignment + sequencing” role.
Distinction from #002 (VRPTW): VRPTW is fleet routing with time windows — multiple vehicles, capacity + time-window constraints. VRPTW also calls shortest path as a subroutine. If time-dependent shortest path is embedded inside VRPTW, the result is traffic-aware fleet routing.
Most-skipped point in the field: detecting negative edges or negative cycles. The practitioner uses Dijkstra in every case; but if there is a negative cost (e.g. a discount on a connection, a capital return, a back-flow rebate, a negative logarithmic edge in a currency-arbitrage cycle) Dijkstra is not optimal — it returns a silently wrong result. Bellman-Ford is needed. If a negative cycle exists, shortest path is undefined (the cycle can be traversed indefinitely, each loop reducing the total). In many financial-arbitrage / network-flow / back-flow scenarios this bug is silent. Bellman-Ford detects a negative cycle if an update still occurs at iteration V.
Second skipped point: algorithmic complexity choice. The practitioner says “Dijkstra works everywhere”; but on a country-scale road network (10M+ edges) a single classical Dijkstra query takes seconds — unacceptable for real-time navigation. Modern preprocessing-based approaches (contraction hierarchies — Geisberger et al. 2008, Transit Node Routing, Hub Labels) deliver sub-millisecond query time on a country-scale graph; preprocessing is a one-time cost (hours-days) but each subsequent query is fast. Third skipped point: the static-graph assumption. Traffic changes in real time; shortest path on a static graph flags “optimum for 14:00” but breaks down at 17:00 rush hour. Time-dependent shortest path (edge weight as a function of time) or rolling-horizon recomputation is essential.
A step-by-step path for an SMB
Stage 1 — Measure first, plan later. At least 6 months of query / route data: daily query volume (how many A-B queries, how many all-pairs queries), average query time, traffic prediction drift (planned vs actual time), route-change rate (recomputation triggers). Road-network inventory: source (map service, OpenStreetMap, own inventory), quality (coverage, freshness, edge-weight type — distance / time / cost), road type (motorway, divided, urban, heavy-vehicle access). Traffic data source: none / inside the map service bundle / separate provider / own GPS fleet data.
Stage 2 — Build the algorithm matrix. Query profile: mostly single point-to-point, mostly single-source all-destinations, all-pairs analysis? Negative-edge / negative-cycle scenarios (financial arbitrage, back-flow)? Graph scale: 1K, 10K, 100K, 1M, 10M+ nodes? Query-time requirement: sub-millisecond (real-time navigation), seconds (planning), minutes (strategic analysis)? Pick the algorithm from this matrix: Dijkstra (small-mid, non-negative), Bellman-Ford (negative edges), Floyd-Warshall (small all-pairs), A* (geographic road network), contraction hierarchies (country-scale real time).
Stage 3 — Pilot. 8-12 weeks. Run the new shortest path engine on a subset of the operation (e.g. the busiest region or the heaviest-query customer segment); the decision still sits with the planner / driver, the engine recommends. Success criterion in writing, beforehand: in the pilot region, fuel -10% minimum, delivery time -15% minimum, query time meets the real-time requirement.
Stage 4 — Rollout. 6-12 months to extend across the full operation + traffic service integration + rolling-horizon recomputation. Quarterly operations committee: shortest path query volume, average query time, traffic prediction drift, route-change rate, network bottleneck report (all-pairs analysis).
Risks — what can go wrong
Traffic prediction drift (static-graph risk). Shortest path on a static graph does not reflect real traffic conditions; the most critical risk. At peak hours the “optimum” route as computed takes longer in reality. Fix: time-dependent shortest path (edge weight as a time function) + traffic data service (5-15 minute refresh) + rolling-horizon recomputation (every 15-30 minutes or event-triggered — accident, closure).
Real-time update lag. If road-closure, accident or traffic-event data arrive at the shortest path engine late, the engine recommends an unknowingly closed road — the driver heads there, turns back, double cost. Fix: event-driven recomputation, real-time traffic-event notification in the driver mobile app, alternative-route suggestion.
Road closure / ban unknown. If the (static) road-network data are not refreshed periodically, new construction, seasonal closure and heavy-vehicle bans are missed; the engine produces infeasible routes. Fix: 3-6-month road-network update cycle, driver field feedback (a “road closed” report in the mobile app), a truck-specific road-network layer for heavy-vehicle routing.
Single-supplier routing-software / map-service lock-in. Without a contract clause for “annual standard-format export (GeoJSON, GraphML, CSV) of road-network data, traffic calibration data, query history and route archive”, leaving the system means losing years of operational data and calibration memory. The contract must explicitly cover road-network data ownership, traffic-calibration parameter export and a standard-format output for the query API.
Solution method — technical view
| Approach | Typical scale | Solve time | Negative edges? |
|---|---|---|---|
| Dijkstra naïve (O(V²)) | Small, V ≤ 1,000 | milliseconds | No |
| Dijkstra binary heap (O((V+E)logV)) | Mid, V ≤ 100K | ms-seconds | No |
| Dijkstra Fibonacci heap (O(E + VlogV)) | Mid-large, V ≤ 1M | seconds | No |
| Bellman-Ford (O(VE)) | Small-mid, negative-edge | seconds-minutes | Yes, detects negative cycle |
| Floyd-Warshall (O(V³)) | Small all-pairs, V ≤ 1,000 | seconds-minutes | Yes (no cycle) |
| Johnson (O(V² logV + VE)) | Mid all-pairs, sparse | minutes | Yes |
| A* (heuristic-guided) | Geographic road network, single point-to-point | ms-seconds | No |
| Bi-directional Dijkstra/A* | Point-to-point, large graph | ms-seconds | No |
| Contraction Hierarchies | Country-scale road network | sub-millisecond (preprocess hours) | No |
| Time-dependent Dijkstra | Traffic-aware road network | ms-seconds | No |
Objective function choice:
- Objective 1 — Minimum total time: Speed-focused; typical for navigation, emergency services, parcel delivery.
- Objective 2 — Minimum total distance: Fuel + vehicle-wear focused; typical for long-haul.
- Objective 3 — Minimum total cost: Weighted sum of fuel + toll + driving hours.
- Objective 4 — Multi-criteria (Pareto-optimum): Trade-off across time + cost + fuel; the decision-maker picks from the Pareto frontier.
Multi-objective: weighted sum (most common) or hierarchical (time first, then cost, then fuel) or Pareto-optimum paths (for advanced decision support).
Shortest path variants — pick by the field:
- Classical Dijkstra: Non-negative edges, single-source, foundational.
- Bellman-Ford: Negative-edge capable, negative-cycle detection, distance-vector routing.
- Floyd-Warshall: All-pairs, small graph, dynamic programming.
- A (Hart-Nilsson-Raphael 1968):* Heuristic-guided point-to-point, geographic road networks.
- Contraction Hierarchies: Country-scale road network, preprocessing-based, real-time.
- Time-dependent shortest path: Traffic-aware, edge weight as a time function.
- Stochastic shortest path (Polychronopoulos-Tsitsiklis 1996): Uncertain edge weights, risk-adjusted.
- Resource-constrained shortest path (RCSP): Additional resource constraints (fuel, time windows); appears as the pricing sub-problem in column-generation VRP.
Academic references
Listed in the page frontmatter under sources.
Sources
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. Foundational two-page paper; one of the most-cited papers in computer science.
- Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90. Foundational reference for Bellman-Ford on negative-edge graphs.
- Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345. Canonical one-paragraph source of all-pairs Floyd-Warshall.
- Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall. Canonical textbook of the network flows and shortest path field.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Teaching reference for Dijkstra / Bellman-Ford / Floyd-Warshall.
- Geisberger, R., Sanders, P., Schultes, D. and Delling, D. (2008). Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Experimental Algorithms (WEA 2008), LNCS 5038, 319-333. Modern preprocessing-based algorithm for country-scale road networks.
- Hart, P. E., Nilsson, N. J. and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. Founding paper of the A* algorithm.
- YÖK Thesis Center — keyword: ’en kısa yol’ or ‘Dijkstra’ or ‘graf algoritması’ — 30+ theses from TR academia. tez.yok.gov.tr
Glossary
- Shortest Path Problem
- Foundational graph-OR problem of finding the minimum total weighted path between two nodes on a weighted graph (single-source single-destination, single-source all-destinations, or all-pairs); polynomial-time algorithms Dijkstra (1959), Bellman-Ford (1958), Floyd-Warshall (1962).
- Dijkstra Algorithm
- Edsger Dijkstra's (1959) polynomial-time algorithm for single-source shortest paths in graphs with non-negative edge weights; greedy — extract the unvisited node with smallest tentative distance from a priority queue and relax its neighbours; O((V+E) log V) with a binary heap.
- MIP
- An optimization model where some decision variables are forced to be whole numbers (e.g. number of trucks, number of shifts).
- VRP
- The decision of which vehicles, leaving from one or more depots, visit which customers in which order.
Related problems
Multiple Plants, Multiple Customers — How Much Does Each Plant Ship to Each Customer to Minimise Total Freight?
For food, packaging or textile producers shipping weekly from 3-8 plants or regional warehouses to 20-100 customers. The weekly decision is: which plant ships how much to which customer, given fixed plant capacities, stated customer demands, and a different per-unit cost (distance + vehicle + contract terms) for each plant-customer pair. The goal is the lowest total freight bill across the network. A 'nearest plant' or 'we've always done it this way' habit typically leaves 10-20% extra fuel and vehicle cost on the table compared with a systematic allocation.
One Vehicle, Many Stops — In What Order Should I Visit Them All to Minimize Total Distance?
You run a field technician visiting 8-15 customers a day (HVAC, lift servicing, white-goods repair), a single-vehicle supplier tour by a sales rep, or a PCB drilling machine sequencing 500-5,000 holes. All of them face the same core call: given N points, in what order should a single vehicle or head visit each one and return to the start. Get the order wrong and a field service vehicle burns 80-200 TRY/day extra in fuel and driver hours, a PCB line takes 15-30% longer per part, and the last customer of the day misses their delivery window. At 50 stops, a hand-built sequence runs 20-40% above the true minimum; as the number of stops grows, the gap from intuitive ordering compounds.