Shortest path problem

The problem of finding a path between specified vertices in a weighted graph whose total edge weight is minimal.

Dijkstra's algorithm: An algorithm that finds shortest paths from one source in a graph with nonnegative edge weights. It repeatedly settles the nearest unreached vertex, making it the standard nonnegative-weight method.
Graph theory: The mathematical study of graphs, structures made of vertices connected by edges. The problem is defined on this structure of vertices and edges.
Routing: The process of selecting paths through a network to carry data or other flows between endpoints. Internet routers use shortest-path methods to choose routes under link-cost metrics.
Longest path problem: The problem of finding a path with maximum total weight between specified vertices. It reverses the objective and is computationally hard in general graphs.
Bellman–Ford algorithm: An algorithm for single-source shortest paths that supports negative edge weights and detects reachable negative cycles. Repeated edge relaxation handles negative weights that invalidate Dijkstra's algorithm.
Weighted graph: A graph whose edges or vertices carry numerical values representing costs, lengths, or other quantities. Its edge weights supply the quantities summed along candidate paths.
Global Positioning System: A satellite-based navigation system that estimates position and time using signals from orbiting satellites. Road-navigation systems commonly apply shortest-path methods to map networks and travel costs.
Traveling salesman problem: The problem of finding a minimum-cost tour that visits every required city and returns to its start. It requires a global visit-and-return tour rather than a route between two vertices.
Floyd–Warshall algorithm: A dynamic-programming algorithm that computes shortest-path distances between every pair of vertices. It solves the all-pairs version by allowing intermediate vertices in a growing set.
Path (graph theory): A sequence of connected vertices in a graph, with consecutive vertices joined by edges. The optimization compares the total weights of these possible routes.

Linked from 28 pages