![]() ![]() You don't need to topologically sort the nodes for that algorithm to work in $O(E V)$ time. 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. 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. 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$.įor general graphs, it isn't obvious how to optimize that, because some paths from $B_i$ to $Z$ may pass through $A$. Problem: Could you please simply explain the logic behind introducing topological sorting and how it helps cutting down complexity to just $O(E V)$? Because of topological ordering, we speed up shortest path finding to just linear time to $O(E V)$. 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. Dijkstra takes $O(E\log)$ 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$. While both work with weighted directed graph, Bellman-Ford algorithm can work with negative edges. Regarding the problem of finding shortest paths, Dijkstra's and Bellman-Ford algorithms are very popular. Suppose we have a DAG (directed acyclic graph). I saw very similar post to mine, but still the answer explains definitions online for topological ordering. ![]() This question is just for discussing algorithms please and not for proposing algorithms. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |