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:
“Jesus wept.”
—Bible: New Testament John, 11:35.
The shortest verse in the Bible; refers to Jesus’ grief at the death of Lazarus, whom he raised from the dead after four days.
“The gray-eyed morn smiles on the frowning night,
Check’ring the eastern clouds with streaks of light,
And fleckled darkness like a drunkard reels
From forth day’s path and Titan’s fiery wheels.”
—William Shakespeare (1564–1616)
“A curious thing about the ontological problem is its simplicity. It can be put in three Anglo-Saxon monosyllables: ‘What is there?’ It can be answered, moveover, in a word—‘Everything.’”
—Willard Van Orman Quine (b. 1908)