求图中节点的单源最短路径可以使用Dijkstra,BellmanFord, SPFA算法，而对于有向无环图DAG来说，可以通过简单的动态规划来进行求解。
DAG的独特之处是所有节点可以线性化（拓扑序列），使得所有边保持从左到右的方向，如下图：
思路
动态规划的递推需要一个线性或者树形的顺序，对于DAG，我们可以将节点按照拓扑顺序来进行线性化，这样就可以来进行递推。
拓扑顺序中节点v排在节点u之后，则只有可能从u到达v，而不能反过来；对于当前的节点v，在拓扑序列中向前查找，可能找到一些可以到达该顶点的其他节点，然后利用 dist[v] = min{dist[u] + w[u][v] | u 可以到达v} 来进行动态规划的递推。
伪码
DagShortestPath(G, w, s){
对节点按照拓扑顺序进行排序
topologically sort the nodes in G
初始化
for each vertex v in G{
dist[v] = INF;
pre[v] = NULL;
}
dist[s] = 0;
//根据拓扑顺序，遍历顶点v
for each v in G, taken in topologically sorted order{
for each edge w[u][v]{
if (dist[v] > dist[u] + w[u][v]){
pre[v] = dist[u] + w[u][v];
pre[v] = u;
}
}
}
}