Directed graph linear algorithm

问题:

I would like to know the best way to calculate the length of the shortest path between vertex s and every other vertex of the graph in linear time using dynamic programming.

The graph is weighted DAG.

回答1:

What you can hope for is an algorithm linear in the number of edges and vertices, i.e. O(|E| + |V|), which also works correctly in presence of negative weights.

This is done by first computing a topological order and then 'exploring' the graph in the order given by this topological order.

Some notation: let's call d'(s,v) the shortest distance from s to v and d(u,v) the length/weight of the arc from u to v (if it exists).

Then, for a node v that is currently being visited, the shortest path from s to v is the minimum of d'(s,u)+d(u,v) for each in-neighbour u of v. In principle, this is very similar to Dijkstra's algorithm except that we already know in which order to traverse the vertices.

The topological sorting ensures that all in-neighbours of v have already been visited and will not be updated again. So, whenever a node has been visited, the distance it is assigned is the correct shortest path from s to v. Therefore, you end up with a shortest s-v-path for each v.

A full description and implementation can be found here, which links to these lecture notes. I'm not sure where the algorithmic idea for this DAG algorithm was originally published in the literature.

This algorithm works for DAGs, even in the presence of negative weights/distances.

While a typical implementation of this algorithm will most likely not be done using dynamic programming explicitly, it can still be interpreted as such since the problem of finding a shortest path to a node v is computed using the shortest paths to the in-neighbours of v. For further discussion on if/how this type of algorithm counts as dynamic programming, let me refer you to this question.

回答2:

It's possible what you're looking for is Bellman-Ford algorithm, which is O(|V||E|) in terms of time complexity (not really linear).

Not sure if some witty dynamic-programming approach could improve on that though.

回答3:

As hauron said, Bellman-Ford will give you what you're looking for in time O(|V||E|). This works even if your graph contains negative weighted edges, and Bellman-Ford uses dynamic programming at its core.

However, I must add that if your weights are non-negative, you can do Dijkstra from your vertex s in time O(|E| log |E|).

回答4:

Initialize d[s] = 0.

For every vertex, calculate:

d[v] = min {d[u] + w(u,v) | (u,v) is an edge}

d[v] = ∞ if v has no incoming edges.

(The algorithm always halts since the graph is acyclic.)