Shortest Path

Path finding is the process of finding a path from a starting vertex to a target vertex in a graph. There are several algorithms for path finding, including Dijkstra’s algorithm, A* search, and Floyd-Warshall algorithm.

Inputs to path finding algorithms typically include: a graph, a starting vertex, and a target vertex.

Output is the shortest path between the starting and target vertices.

Formally, a path is a sequence of vertices in a graph such that each vertex is adjacent to the next vertex in the sequence.

The length of a path is the sum of the weights of the edges between the vertices in the path.

Generally, path finding algorithms can be classified into two categories:

  1. Single-source Shortest Path Algorithms: These algorithms find the shortest path from a single source vertex to all other vertices in the graph. Examples include Dijkstra’s algorithm and Bellman-Ford algorithm.

  2. All-pairs Shortest Path Algorithms: These algorithms find the shortest path between all pairs of vertices in the graph. Examples include Floyd-Warshall algorithm.

BFS: unweighted graphs

In an unweighted graph, all edges have the same weight, typically 1.

In case of an unweighted graph, the shortest path found by BFS is guaranteed to be the shortest path in terms of the number of edges.