Channi Studies

A topological sort of a directed, acyclic graph produces a list of graph's vertices such that for every edge from a vertex X to a vertex Y, X comes before Y in the list. There can be more than one valid topoligcal sort. Again, the graph must be acyclic and riected in order to apply topological sorting. The time complexity and space complexity of topological sorting is O(|V| + |E|).

The Bellman-Ford shortest path algorithm, created by Richard Bellman and Lester Ford, Jr,. determines the shortest path from a start vertex to each vertex in a graph. For each vertex, the Bellman-Ford algorithm determines the vertex's distance and predecessor pointer. A vertex's distance is the shortest path distance from the start vertex. A vertex's predecessor pointer points to the previous ve..