## Introduction

The shortest path issue in graph theory is the task of finding a path between two vertices (or nodes) in a graph that minimizes the sum of the weights of its constituent edges.

The challenge of determining the shortest way between two junctions on a road map may be described as a specific example of the shortest path problem in graphs, where the vertices correspond to intersections and the edges to road segments, each of which is weighted by the segment's length.

###
Different algorithms for shortest path** **

The most important algorithms for solving this problem are

- With non-negative edge weight, Dijkstra's method solves the single-source shortest route issue.
- If edge weights are negative, the Bellman-Ford algorithm solves the single-source problem.
- The A* search algorithm uses heuristics to try to speed up the search for the single-pair shortest path.
- All-pairs shortest routes are solved using the Floyd–Warshall method.
- On sparse graphs, Johnson's technique solves all-pairs shortest routes quicker than Floyd–Warshall.
- With extra probabilistic weight on each node, the Viterbi algorithm solves the shortest randomized route issue

## Djikstra’s Algorithm

We use the graph cost adjacency matrix, where cost is the edge's weight, represents the graph. The diagonal values in the graph's cost adjacency matrix are 0 because the source and destination vertex are the same. It is denoted by +∞ if there is no path from source vertex Vs. to any other vertex Vi. We assumed that all weights were positive in this algorithm. **Dijkstra's algorithm never ends if the graph contains at least one negative cycle**. By a negative cycle, we mean a cycle that has a negative total weight for its edges. Stepwise Implementation:

- Create an empty set 'minCost' of size equal to the number of vertices to store the minimum cost to reach a particular vertex from the source vertex Vs.
- Initially include the source vertex Vs. in set minCost and determine all the other direct paths from the source vertex Vs., without going through any other vertex.
- Now include the nearest vertex in set minCost from the source vertex Vs. Again, find the shortest paths to all other vertex using this nearest vertex and update the values.
- Keep repeating this step for n-1 times to include n-1 vertices, where n is the total number of vertices in the graph.

After completing the above steps, we will get the shortest path to all other vertices from the source vertex.

**Example:**

Find the Shortest path between P and Q in the given graph using Djikstra’s Algorithm.

**Step 1: **Make the empty set minCost, which will hold the shortest path from the source vertex P.

**Step 2**: Include the source vertex P in the set minCost, and find the direct shortest path to all other vertices without using any other vertex.

minCost | P | A | B | C | D | Q |

P | 0 | 8(P) | ∞ | 4(K) | ∞ | 40(K) |

**Step 3**: Include the vertex nearest to P, which is C in this case, and again find the shortest path using vertex C, and update the values.

minCost | P | A | B | C | D | Q |

P | 0 | 6(P,C) | 14(P,C) | 4(K) | 16(P,C) | 36(P,C) |

**Step 4**: Include the vertex 2nd nearest to P, which is A in this case, and again find the shortest path using vertex C and A, and update the values.

minCost | P | A | B | C | D | Q |

P | 0 | 6(P,C) | 14(P,C) | 4(K) | 14(P,C,A) | 36(P,C) |

**Step 5**: Include the vertex 3rd nearest to P, which is B in this case, and again find the shortest path using vertex C, A, and B, and update the values.

minCost | P | A | B | C | D | Q |

P | 0 | 6(P,C) | 14(P,C) | 4(K) | 14(P,C,A) | 16(P,C,B) |

**Step 6**: Again include the vertex next nearest to P, which is D in this case, and again find the shortest path using C, A, B, and D, and update the values.

minCost | P | A | B | C | D | Q |

P | 0 | 6(P,C) | 14(P,C) | 4(K) | 14(P,C,A) | 16(P,C,B) |

Since all the n-1 vertices are included, and hence we get the shortest distance between P and Q = 16, and the shortest path between P and Q is P->C->B->Q.