Shortest Path
Definition
The shortest path problem seeks a path with minimal total cost between nodes of a graph.
Depending on edge weights and problem structure, algorithms like Dijkstra, Bellman-Ford, or A* are applicable.
Simply explained
How to find the cheapest route through a network.
Why it matters in practice
Relevant for routing, planning, networks, and process graphs.
Example from business
A logistics system searches for the route with the lowest travel time between warehouse and customer.
Limits and pitfalls
- Do not confuse "shortest" with the fewest edges; do not use negative weights unchecked; ignore dynamic costs.
Origin & history
Dijkstra published a fundamental algorithm for shortest paths with nonnegative edge weights in 1959.
Use in mid-sized companies
- Possible application in SMEs: Model routing or process costs as a graph and choose the appropriate algorithm.
Frequently asked questions
Is Dijkstra always suitable?
No, negative edges or other problem structures require different methods.
Sources
- A note on two problems in connexion with graphs · Dijkstra (1959), A note on two problems in connexion with graphs
- single_source_dijkstra · NetworkX, single_source_dijkstra
Source verification: 10./12.10.2026.
Editorially reviewed on: