Which of the following algorithms solves the single-source shortest paths?

Concept:

Single source shortest path problem finds the shortest path from a source node to all other nodes in a graph.

Explanation:

Dijkstra’s algorithm is used to solve the single source shortest path problem.

Key points for this:

• It is used for both directed and undirected graphs.
• All edges must have non - negative weights.
• Graph must be connected

Algorithm of dijkstra’s algorithm is:

1) dis[s] <- 0 / distance to source node is 0

2) for all vertices v except source vertex

3) do dist[v] -> infinity

4) s -> empty / initially there are no visited nodes, set is empty

5) while Q <- v / queue contains all nodes

6) while Q is not empty

7) do u -> mindistance (Q, dist) / select node from queue having minimum distance

8) S-> S U {node} / add that selected node to the set (list of visited nodes)

9) for all vertices that are neighbours of node

10) do if dist[v] > dist[node] + w(u, v)

11) then d[v] -> d[node] + w[u,v] / new value for shortest path is set