**Single source shortest path problem ( Dijkstra’s Algorithms )**

Shortest path problem is nothing but it is a problem of finding a path between two vertices or two nodes in a graph so that the sum of the weights of its constituent edges in graph is minimized.

- This problem is to determine shortest paths from a given source vertex v to all remaining destination vertices
- This problem can be solved by using Greedy method
- Edsger Dijkstra finds the shortest path between two given nodes and developed a solution called Dijkstra’s Algorithms For a given source node in the graph, the algorithm searches for the shortest path between this node and all others. This algorithm also be used to find shortest paths from a single node to a single destination node by stopping the algorithm once when the shortest path to the destination node has found
- Shortest paths are built one by one as a multi-stage solution
- Let
*S*= set of vertices (including*v*) to which the shortest paths have already been generated_{0 }*dist(w)*= length of shortest path starting from*v*, going through only those vertices that are in_{0}*S*, and ending at*w* - If the next shortest path is to vertex
*u*, then the path begins at*v*ends at_{0},*u*, and goes through only those vertices that are in*S*. - The destination of the next path generated must be that of vertex
*u*which has the minimum distance,*dist(u),*among all vertices not in*S*. - Having selected a vertex
*u*as in observation 2 and generated the shortest*v*to_{0 }*u*path, vertex*u*becomes a member of*S*. - An algorithm for Single source shortest path problem Using Dijkstra’s Algorithms is given below:
**Time complexity of Dijkstra’s algorithm**is**O(n**^{2})

**Example:**

Its cost adjacency matrix and shortest path values table are given below. In the cost adjacency matrix, all entries not shown are +**∞**.

Topic : Single source shortest path | Dijkstra’s Algorithms

nice site