我想知道使用动态编程计算线性时间中顶点s和图形的每个其他顶点之间的最短路径长度的最佳方法。
该图是加权DAG。
您可以期待的是边缘和顶点数量的线性算法，即O(|E| + |V|)，它也可以在负权重的情况下正常工作。
这是通过首先计算拓扑顺序然后按照该拓扑顺序给出的顺序“探索”图形来完成的。
一些符号：让我们称d'(s,v)是从s到v和d(u,v)的最短距离，从u到v（如果存在的话）弧的长度/重量。
然后，对于当前正在访问的节点v，从s到v的最短路径是d'(s,u)+d(u,v)的每个邻居u的v的最小值。原则上，这与Dijkstra算法非常相似，只是我们已经知道遍历顶点的顺序。
拓扑排序确保v的所有邻居都已被访问过，并且不会再次更新。因此，每当访问一个节点时，它所分配的距离就是从s到v的正确最短路径。因此，您最终会为每个v提供最短的s-v路径。
完整的描述和实现可以找到here，链接到these lecture notes。我不确定这个DAG算法的算法思想最初是在文献中发表的。
即使在负权重/距离存在的情况下，该算法也适用于DAG。
虽然这种算法的典型实现很可能不会明确地使用动态编程来完成，但它仍然可以这样解释，因为找到到节点v的最短路径的问题是使用到v的邻居的最短路径来计算的。 。有关此类算法是否/如何算作动态编程的进一步讨论，请转帖给this question。
您可能正在寻找的是Bellman-Ford算法，就时间复杂度而言是O（| V || E |）（非线性）。
不确定一些诙谐的动态编程方法是否可以改进。
正如hauron所说，Bellman-Ford将及时为你提供你想要的东西O（| V || E |）。即使您的图形包含负加权边缘，这也适用，而Bellman-Ford的核心使用动态编程。
但是，我必须补充一点，如果你的权重是非负的，你可以在时间O（| E | log | E |）中从你的顶点做Dijkstra。
初始化d[s] = 0。
对于每个顶点，计算：
d[v] = min {d[u] + w(u,v) | (u,v) is an edge}
如果d[v] = ∞没有传入边缘，v。
（由于图形是非循环的，因此算法总是停止。）