Shortest Path Concepts and Dijkstra's Algorithm

Flashcards defining key terms and concepts related to the shortest path problem and Dijkstra's algorithm.

Dijkstra's Algorithm

An algorithm used to find the shortest path from a source node to other nodes in a graph.

Shortest Path Problem

Finding the shortest directed path from a source node to a destination node in a graph.

Directed Graph

A graph in which the edges have a direction, indicating what node can be reached from another.

Edge Length

The weight or cost associated with an edge in a graph that affects the total path length.

Priority Queue

A data structure that maintains elements prioritized by keys, allowing for efficient access to the highest priority element.

Admissible Heuristic

A heuristic that never overestimates the cost to reach the goal, ensuring optimality in algorithms like A*.

Heap

A complete binary tree implementation used for efficiently managing a priority queue with insert and delete-min operations.

Branch and Bound

An algorithm design paradigm for solving combinatorial and optimization problems, using bounding to prune non-promising paths.

Straight Line Distance (SLD)

A heuristic measure representing the shortest distance between two points, often used in pathfinding.

Cut (in search algorithms)

Pruning of paths that cannot lead to an optimal solution based on current information.

Explored Nodes

The set of nodes in a graph for which the shortest path distance has already been determined.

Cost of Path

The total length or weight of a path calculated by summing the lengths of its edges.

Graph Exploration

The process of visiting nodes and edges in a graph to determine the shortest path.

Heuristic Search

A search strategy that uses heuristics to guide the exploration of paths to find solutions more efficiently.