Shortest Path Algorithms

SHORTEST PATH ALGORITHMS:

An algorithm to find the shortest distance path between the source and destination vertices is called the shortest path algorithm.

Types of shortest path problem

i.   Single source shortest path

Given an input graph G = (V,E) and a distinguished vertex S, find the shortest path from S to every other vertex in G.

Example: Dijkstra‟s algorithm (weighted graph and unweighted graph).

ii.  All pairs shortest path problem

Given an input graph G = (V,E). Find the shortest path from each vertex to all vertices in a graph.