![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/3b/Shortest_path_with_direct_weights.svg/640px-Shortest_path_with_direct_weights.svg.png&w=640&q=50)
Shortest path problem
Computational problem of graph theory / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Shortest path?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
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 article includes a list of general references, but it lacks sufficient corresponding inline citations. (June 2009) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3b/Shortest_path_with_direct_weights.svg/320px-Shortest_path_with_direct_weights.svg.png)
The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment.