1
$\begingroup$

This question is just for discussing algorithms please and not for proposing algorithms. I saw very similar post to mine, but still the answer explains definitions online for topological ordering.

Suppose we have a DAG (directed acyclic graph). Regarding the problem of finding shortest paths, Dijkstra's and Bellman-Ford algorithms are very popular. While both work with weighted directed graph, Bellman-Ford algorithm can work with negative edges. Dijkstra takes $O(E\log{E})$ while Bellman-Ford algorithm takes $O(EV)$ to execute, where $E$ is the number of edges and $V$ is the number of vertices in graph $G$.

Now here comes my issue, topological ordering works by just numbering the order by which we will visit the vertices of a graph and it works with negative edges as well, so this is a pro over Dijkstra. Because of topological ordering, we speed up shortest path finding to just linear time to $O(E+V)$.

Problem: Could you please simply explain the logic behind introducing topological sorting and how it helps cutting down complexity to just $O(E+V)$?

$\endgroup$
7
  • $\begingroup$ BFS only works for unweighted graphs. $\endgroup$ Sep 20 at 17:35
  • 1
    $\begingroup$ Your post doesn't contain the word DAG. Hence my confusion. $\endgroup$ Sep 20 at 17:47
  • 1
    $\begingroup$ Also, Dijkstra's name is spelled without an e. $\endgroup$ Sep 20 at 17:47
  • 1
    $\begingroup$ The other algorithms you mention work on general graphs. In the special case of DAGs, simpler (and faster) algorithms work. It doesn't get any deeper than that. $\endgroup$ Sep 20 at 17:51
  • 4
    $\begingroup$ Well, it's not magic. Like any valid algorithm, there is an idea behind it, and you can prove that it works. I recommend any decent textbook. $\endgroup$ Sep 20 at 17:55
1
$\begingroup$

The shortest path between vertices $A$ and $Z$ (where $A\ne Z$) is the minimum over all edges $A\to B_i$ of the weight of that edge plus the shortest path from $B_i$ to $Z$.

For general graphs, it isn't obvious how to optimize that, because some paths from $B_i$ to $Z$ may pass through $A$.

In a dag, that can't happen, and so there is an easy algorithm: compute and cache the shortest path from each vertex to $Z$ the first time you encounter the vertex, and look up the cached value if you reach the same vertex again. If you use a data structure with $O(1)$ insertion and lookup, such as a hash table, or a simple array if the nodes are identified by consecutive integers, then this runs in $O(E+V)$ time, because you do constant work for each first encounter of a vertex, constant work for each edge, and constant work for each subsequent encounter of a vertex, and there are fewer than $E$ subsequent encounters in total.

You don't need to topologically sort the nodes for that algorithm to work in $O(E+V)$ time. If you happen to know the topological order, then you can use it in a dynamic-programming version of the algorithm, which has the same asymptotic run time but may have smaller constant factors. But it isn't topological sorting that enables a linear-time algorithm; it's the fact that you know the graph is a dag.

$\endgroup$
1
  • $\begingroup$ Thank you. What do you think distinguishes DAG in your opinion please from other graphs besides general properties of DAG if possible? $\endgroup$
    – Avra
    Sep 20 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.