Shortest Path Algorithms | Shortest Path Problems

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-

 

  1. Google Maps
  2. Road Networks
  3. Logistics Research

 

Types of Shortest Path Problem-

 

There are different types of shortest path problem-

 

  1. Single-pair shortest path problem
  2. Single-source shortest path problem
  3. Single-destination shortest path problem
  4. 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
Shortest Path Algorithms | Shortest Path Problems
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
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-