# Shortest Path Algorithms

## Shortest Path Algorithms

For a given graph, the shortest path algorithms determine the minimum cost of the path from source vertex to every vertex in a graph.

Path is the movement traced across sequence of vertices V_{1}, V_{2}, V_{3},....,V_{N} in a graph. Cost of the path is the sum of the cost associated with all the edges in a graph. This is represented as:

- If the graph is weighted, then the cost of the path is the sum of weights on its edges.
- If the graph is not weighted, the cost of the path is the number of edges on the path.

### Where does the shortest path algorithm find its applications?

- We can use the shortest path algorithm to find the cheapest way to send the information from one computer to another within a network.
- We can use the shortest path algorithm to find the best route between the two airports.
- We can use to find a road route which requires minimum distance from a starting source to an ending destination. We can determine the route which requires minimum time to an ending destination

### Shortest path Problems

- There are different kinds of shortest-path problems.
**The single source shortest path problem**is used to find minimum cost from single source to all other vertices.**The all-pairs shortest path problem**is used to find the shortest path between all pairs of vertices.

- The single source shortest path problem is solved by using
**Dijkstra's algorithm**and the all-pairs shortest-path problem is solved by using**Floyd-Warshall Algorithm**. Let us look at Dijkstra's algorithm.