Shortest path problem: Difference between revisions

Revision as of 16:44, 6 April 2024

Revision as of 20:07, 6 April 2024

Line 1:

{{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, G) 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.