Dijkstra's algorithm

Dijkstra's algorithm finds shortest paths from a source vertex in a weighted graph with nonnegative edge weights. It repeatedly finalizes the unsettled vertex with the smallest known distance.

Edge relaxation: A graph operation that improves a vertex's distance estimate using a path through an adjacent vertex. Dijkstra's algorithm applies relaxation whenever it processes an outgoing edge.
Graph theory: The mathematical study of graphs, structures made of vertices connected by edges. Dijkstra's algorithm operates on weighted graphs and their paths.
Bellman–Ford algorithm: A shortest-path algorithm that handles negative edge weights and detects reachable negative cycles. Unlike Dijkstra's algorithm, it remains valid when some edge weights are negative.
Road network: A graph model of roads and intersections, with edges often weighted by distance or travel time. Road-routing systems use shortest-path methods to compare routes from a starting location.
Priority queue: An abstract data structure that retrieves elements according to priority. It selects the unsettled vertex with the smallest tentative distance.
Weighted graph: A graph whose edges carry numerical values representing quantities such as distance or cost. The algorithm compares sums of edge weights to rank paths.
Breadth-first search: A graph traversal that explores vertices in increasing numbers of edges from a starting vertex. It finds shortest paths by edge count when all edges have equal cost.
Internet routing: The process of selecting paths for data packets across interconnected networks. Link-state routing protocols use Dijkstra's algorithm to compute routes from a router.
Greedy algorithm: An algorithmic strategy that repeatedly makes a locally optimal choice. Finalizing the nearest unsettled vertex is Dijkstra's greedy choice.
Path (graph theory): A sequence of vertices connected by consecutive edges in a graph. The algorithm seeks paths whose total edge weight is minimal.

Linked from 19 pages