Which algorithm efficiently calculates the single source shortest paths in a Directed Acyclic Graph

The algorithm that efficiently calculates the single source shortest paths in a Directed Acyclic Graph (DAG) is the Topological Sort algorithm. Here are the steps:

1. Topologically sort the nodes of the graph. This can be done using Depth-First Search (DFS). Start from the source node, visit all its adjacent nodes. If the adjacent node has already been visited, skip it. If not, recursively visit all its adjacent nodes before marking it as visited. Repeat this process until all nodes have been visited. The topological sort of the nodes is the reverse of the order in which the nodes are marked as visited.

2. Initialize the distance to the source node as 0 and to all other nodes as infinity.

3. For each node, taken in topological order, relax all its adjacent nodes. To relax an edge means to update the shortest distance to the destination node of the edge. If the current shortest distance to the destination node is greater than the sum of the shortest distance to the source node and the weight of the edge, update the shortest distance to the destination node.

4. After all nodes have been processed, the shortest distances to all nodes have been calculated.

This algorithm works because in a DAG, once a node has been processed, the shortest distance to it has been finalized. There are no cycles, so we won't process a node again, which guarantees that we won't get stuck in an infinite loop. The time complexity of this algorithm is O(V+E), where V is the number of nodes and E is the number of edges, which is very efficient.