Shortest Path Algorithms

Given a weighted graph and two vertices u and v we want to find a path of minimum total weight between u and v.

• Single Source: find a shortest path from a given source (vertex s) to each of the vertices.

• Single Pair: Given two vertices, find a shortest path between them.

Properties

• a subpath of a shortest path is itself a shortest path

• There is a tree of shortest paths froma. start vertex to all the other vertices

Best-First search is an informed search algorithm that prioritizes nodes with the most promising heuristic value, aiming to find a solution quickly by expanding the node that appears closest to the goal

A heuristic equation is estimated guessing.