Introduction to All-Pairs Shortest Paths

Learn about the history and evolution of all-pairs shortest paths algorithms.

Shortest path tree

Previously, we discussed several algorithms to find the shortest paths from a single source vertex ss to every other vertex of the graph by constructing the shortest path tree rooted at ss. The shortest path tree specifies two pieces of information for each node vv in the graph:

  • dist(v)dist(v) is the length of the shortest path from ss to vv.
  • pred(v)pred(v) is the second-to-last vertex in the shortest path from ss to vv.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy