In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
This is analogous to the problem of finding the shortest path between two intersections on a road map: the graph's vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of its road segment.
Read more about Shortest Path Problem: Definition, Algorithms, Roadnetworks, Applications, Related Problems, Linear Programming Formulation
Famous quotes containing the words shortest, path and/or problem:
“The Gettysburg speech is at once the shortest and the most famous oration in American history. Put beside it, all the whoopings of the Websters, Sumners and Everetts seem gaudy and silly. It is eloquence brought to a pellucid and almost gem-like perfection—the highest emotion reduced to a few poetical phrases.”
—H.L. (Henry Lewis)
““O what unlucky streak
Twisting inside me, made me break the line?
What was the rock my gliding childhood struck,
And what bright unreal path has led me here?””
—Philip Larkin (1922–1986)
“Great speeches have always had great soundbites. The problem now is that the young technicians who put together speeches are paying attention only to the soundbite, not to the text as a whole, not realizing that all great soundbites happen by accident, which is to say, all great soundbites are yielded up inevitably, as part of the natural expression of the text. They are part of the tapestry, they aren’t a little flower somebody sewed on.”
—Peggy Noonan (b. 1950)