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:
“I have simplified my politics into an utter detestation of all existing governments; and, as it is the shortest and most agreeable and summary feeling imaginable, the first moment of an universal republic would convert me into an advocate for single and uncontradicted despotism. The fact is, riches are power, and poverty is slavery all over the earth, and one sort of establishment is no better, nor worse, for a people than another.”
—George Gordon Noel Byron (1788–1824)
“The lesson which these observations convey is, be, and not seem. Let us acquiesce. Let us take our bloated nothingness out of the path of the divine circuits. Let us unlearn our wisdom of the world. Let us lie low in the lord’s power, and learn that truth alone makes rich and great.”
—Ralph Waldo Emerson (1803–1882)
“The problem ... is emblematic of what hasn’t changed during the equal opportunity revolution of the last 20 years. Doors opened; opportunities evolved. Law, institutions, corporations moved forward. But many minds did not.”
—Anna Quindlen (b. 1952)