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 shortest answer is doing.”
—English proverb, collected in George Herbert, Jacula Prudentum (1651)
“But the path of the righteous is like the light of dawn, which shines brighter and brighter until full day. The way of the wicked is like deep darkness; they do not know what they stumble over.”
—Bible: Hebrew, Proverbs 4:18-19.
“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)