Editing Shortest path problem (section)

{{short description|Computational problem of graph theory}}
{{More footnotes needed|date=June 2009}}
[[File:Shortest path with direct weights.svg|thumb|upright=1.2|Shortest path (A, C, E, D, F), blue, between vertices A and F in the weighted directed graph]]
In [[graph theory]], the '''shortest path problem''' is the problem of finding a [[path (graph theory)|path]] between two [[vertex (graph theory)|vertices]] (or nodes) in a [[Graph (discrete mathematics)|graph]] such that the sum of the [[Glossary of graph theory terms#weighted graph|weights]] of its constituent edges is minimized.<ref>{{Cite book |url=https://link.springer.com/book/10.1007/978-3-031-02574-7 |title=The Shortest-Path Problem |series=Synthesis Lectures on Theoretical Computer Science |date=2015 |language=en |doi=10.1007/978-3-031-02574-7|isbn=978-3-031-01446-8 }}</ref>

The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length or distance of each segment.