Which algorithm efficiently calculates the single source shortest paths in a Directed Acyclic Graph?ans.topological sort hash tablebinary searchradix sort

The algorithm that efficiently calculates the single source shortest paths in a Directed Acyclic Graph is the topological sort.

Here's a step-by-step explanation:

1. Topological Sort: This is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u, v), vertex u comes before v in the ordering. It can be used to efficiently calculate the shortest paths in a DAG.

2. Initialize distances: Initialize all distances as infinite (or a very large number), except the distance of the source vertex, which should be 0.

3. Create a topological order: Use the topological sort algorithm to create a linear ordering of the vertices.

4. Process vertices in topological order: For every vertex u in topological order, update the distance of all adjacent vertices of u. If the distance to an adjacent vertex v is smaller through u, then update the distance of v.

5. The final distances: After all vertices are processed, the final distances from the source vertex to all other vertices are the shortest paths.

This algorithm works because in a DAG, the edges can only go from a vertex to a vertex later in the topological order, so when we're processing a vertex, we've already processed all vertices that have edges to it.