For 10 points, name this class of algorithms which determines the minimum sum of the weights between two nodes of a graph, exemplified by the quickest way to get between two cities given the time spent on roads between them.
Fibonacci heaps are used in Johnson's Algorithm to determine this, and an efficient way to determine it via a best-first method is A* [A-STAR]. One variety of this class of algorithms runs in N cubed time in the size of the graph and is the all-pairs approach, which is slower than the Bellman-Ford algorithm of this type. The simplest algorithm for determining this involves a single source and a single destination with nonnegative edge weights and is named for Dijkstra. For 10 points, name this class of algorithms which determines the minimum sum of the weights between two nodes of a graph, exemplified by the quickest way to get between two cities given the time spent on roads between them.
Fibonacci heaps are used in Johnson's Algorithm to determine this, and an efficient way to determine it via a best-first method is A
{shortest}-{path} algorithms [accept clear equivalents; prompt on “graph search”, “tree search”, or anything else involving searching]