# DAG algorithm

DAG algorithm is based on the following observation: if we know all arcs (u, v) with u in the cloud and v outside the cloud. We know all shortest paths to u, so we can compute d(v ) = min{d(u) + weight(u, v)}. DAG algorithm is a greedy dynamic programming algorithm (similar to a bread first search), it visits all possible solutions.

Conditions.

• No cycle
• Directed graph
• Finite number of vertices
• A defined source

This algorithm takes as input an oriented graph weighted by positive real numbers and a source vertex. The algorithm gradually builds a subgraph in which the different vertices are classified in ascending order of their minimum distance to the starting vertex. The distance is the sum of the weights of the borrowed arcs.

Initially, we consider that the distances from each vertex to the starting vertex are infinite except for the starting vertex for which the distance is 0. The starting subgraph is the empty set.

During each iteration, we choose a vertex outside the subgraph such that all its successors are in the subgraph and we add it to the subgraph. Then, we update the distances of its succesors. The update takes place as follows: the new distance from the neighboring vertex is the minimum between the existing distance and that obtained by adding the weight of the arc to the value of the added one.

This continues until the vertices are exhausted (or until the end vertex is reached).   For practical reasons, the resolution of the DAG algorithm only returns an array containing the visited vertex, the list of predecessors (the vertices already validated) and the values of the shortest paths to all the other vertices that are updated. Which corresponds to a current line of the table presented.

Optimality

A vertex is validated if all its predecessors are validated. We know the shortest way of all its predecessors. In the initial state, we have validated the origin and we know the path of size 1 starting from the origin. The next vertex to validate therefore has a path with only validated vertices. By recurrence we deduce that we have validated the shortest path from the origin to this vertex.

```D = 0;
For each vertex i do
C[i] = 0; D[i] = L[1, i];
For k = 1 to n - 1 do
For each vertex i which is a successor of k do
if (D[k] + L[k, i] < D[i]) then
D[i] = D[k] + L[k, i];
C[i] = k;
end
end
end
Return D
```