Tag Archives: Khan’s algorithm

Topological Sort

Besides, traversing and searching shortest path in a graph, you can sort vertices in directed acyclic graph. This type of sorting is called topological sort and it can be useful in task scheduling application. The tasks can have dependencies on other tasks. These dependencies can be simple, then we can arrange the tasks in a linked list and execute task one by one. In case if we have more that one dependency, then we will use DAG, to represent these tasks.

gag_toposort

The topological sorting can be applied only on DAG, because cycle doesn’t give a chance to prioritize tasks. Continue reading Topological Sort