Another approach uses dynamic programming, and checks all edges n times; that algorithm also detects negative cost cycles, and is named for Bellman and Ford.
Zhan and Noon tested algorithms for solving this problem, finding approximate or double bucket modifications to one algorithm and Pallattino's algorithm with two queues were fastest on actual data. Johnson's algorithm solves this problem in the sparse case faster than the cubic Floyd's algorithm, both of which solve this for all pairs. Another approach uses dynamic programming, and checks all edges n times; that algorithm also detects negative cost cycles, and is named for Bellman and Ford. A Fibonacci heap is used to speed up a greedy approach, which works only for positive-weight edges, while if an admissible heuristic is available, the A* algorithm can be used. For 10 points, identify this problem in graph theory, most famously solved by Dijkstra's algorithm, which asks for a fast route between two nodes.
Zhan and Noon tested algorithms for solving this problem, finding approximate or double bucket modifications to one algorithm and Pallattino's algorithm with two queues were fastest on actual data.
{shortest path} algorithms [accept with any of the following modifying the answer: all-pairs, single-source, or single-source single-destination]