**Shortest Path Problem-**

- In general, Shortest path problem is a problem of finding the shortest path(s) between vertices or nodes in the given graph.
- Shortest path between two vertices is a path that has the least cost as compared to all other paths that exists in the graph.

**Shortest Path Algorithms-**

- Shortest path algorithms are a family of algorithms used for solving shortest path problem.
- Shortest path algorithms have a wide range of applications such as in-

- Google Maps
- Road Networks
- Logistics Research

**Types of Shortest Path Problem-**

There are different types of shortest path problem-

- Single-pair shortest path problem
- Single-source shortest path problem
- Single-destination shortest path problem
- All pairs shortest path problem

**1. Single-pair shortest path problem-**

- Single-pair shortest path problem is a shortest path problem in which we find out the shortest path between a pair of vertices of the given graph.
**A* Search Algorithm**is a famous algorithm used for solving single-pair shortest path problem.

**2. Single-source shortest path problem-**

- Single-source shortest path problem is a shortest path problem in which we find out the shortest paths from a given source vertex to all the other remaining vertices of the given graph.
**Dijkstra’s Algorithm**and**Bellman Ford Algorithm**are the famous algorithms used for solving single-source shortest path problem.

**3. Single-destination shortest path problem-**

- Single-destination shortest path problem is a shortest path problem in which we find out the shortest paths from all the vertices to a single destination vertex of the given graph.
- By reversing the direction of each edge in the graph, this problem is reduced to a single-source shortest path problem.
**Dijkstra’s Algorithm**is a famous algorithm adapted for solving single-destination shortest path problem.

**4. All pairs shortest path problem-**

- All pairs shortest path problem is a shortest path problem in which we find out the shortest paths between every pair of vertices of the given graph.
**Floyd-Warshall Algorithm**and**Johnson’s Algorithm**are the famous algorithms used for solving All pairs shortest path problem.

Get more notes and other study material of **Design and Analysis of Algorithms (DAA)**.

Watch video lectures by visiting our YouTube channel **LearnVidFun**.

Summary

Article Name

Shortest Path Algorithms | Shortest Path Problems

Description

Shortest path problem is a problem of finding the shortest path(s) between vertices or nodes in the given graph. Shortest path algorithms are a family of algorithms used for solving shortest path problem.

Author

Akshay Singhal

Publisher Name

Gate Vidyalay

Publisher Logo