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 purifying, healing influence of literature, the dissipating of passions by knowledge and the written word, literature as the path to understanding, forgiveness and love, the redeeming might of the word, the literary spirit as the noblest manifestation of the spirit of man, the writer as perfected type, as saint.”
—Thomas Mann (1875–1955)
“I tell you, sir, the only safeguard of order and discipline in the modern world is a standardized worker with interchangeable parts. That would solve the entire problem of management.”
—Jean Giraudoux (1882–1944)