Shortest path problem: Difference between revisions

Revision as of 19:17, 7 November 2023

Revision as of 09:53, 10 November 2023

Line 2:

{{More footnotes needed|date=June 2009}}

[[File:Shortest path with direct weights.svg|thumb|upright=1.2|Shortest path (A, C, E, D, F) between vertices A and F in the weighted directed graph]]

In [[graph theory]], the '''shortestlongest 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.

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 of the segment.